Hexokmp

kmp

Created2025-09-08|Updated2025-09-26
|Post Views:

KMP 算法

在线性的时间和空间复杂度中查询字串s在文本t 中出现的次数,linux中grep命令实现

[前缀函数与 KMP 算法 - OI Wiki]:

Author: Ricky Shao
Link: http://example.com/2025/09/08/kmp/
Copyright Notice: All articles on this blog are licensed under CC BY-NC-SA 4.0 unless otherwise stated.
Previous
高级算法
高级算法 在大二下学期学习了yyt老师主讲的概率论与数理统计,作为拔尖班课程,yyt老师掺杂了很多有关随机算法,组合数学的私货,于是在大三上学期继续修读由yyt老师开设的高级算法。 课程网站:TCS Wiki Min-cut一个非常经典的图论模型与算法,笔者在大二上学习了最大流最小割定理,之后学习了解决该问题的随机算法Karger's Algorithm,原理十分简单,只需要有基本的图论与条件概率的知识即可。 这里是一篇讲义,读者可自行参考CS161Lecture16.pdf。 当我们找到了图G的最小割时,图的节点被分为两个互不相交的集合S和T,其中一条边若连接着分别属于这两个集合的顶点,那么这条边就属于当前划分的割。Karger算法将集合S,T视为两个super node。集合内部的边均可收缩,因为对最小割的寻找没有影响。 算法过程123for (int i=1;i<=n-2;i++)...
Next
graph-matrix
谱图论引言笔者在大二上学期学习了图论与算法的相关内容,并且有一定的离散数学基础,不过谱图论作为单纯使用线性代数手法分析图的邻接矩阵等性质的一门学科,笔者从未接触过。 拉普拉斯矩阵
avatar
Ricky Shao
Articles
11
Tags
0
Categories
0
Follow Me
Announcement
南京大学匡亚明学院计算机方向大三在读
Contents
  1. 1. KMP 算法
Recent Posts
数学分析随笔2025-09-22
并行计算2025-09-15
graph-matrix2025-09-10
kmp2025-09-08
K近邻算法2025-09-03
©2019 - 2025 By Ricky Shao
Framework Hexo 7.3.0|Theme Butterfly 5.3.5