kmp（看毛片）算法

别人的两篇博客。

传送门1

传送门2

摘录：

其中T为主串，P为模式串。

其实就是在T中找P。

其中next数组存的是“部分匹配值”。

"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，

－　"A"的前缀和后缀都为空集，共有元素的长度为0；

－　"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；

－　"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；

－　"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；

－　"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；

－　"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；

－　"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

"部分匹配"的实质是，有时候，字符串头部和尾部会有重复。比如，"ABCDAB"之中有两个"AB"，那么它的"部分匹配值"就是2（"AB"的长度）。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度部分匹配值），就可以来到第二个"AB"的位置。

1 #include <cstdio> 2 #include <cstring> 3 4 int lenT, lenP; 5 int next[1001]; 6 char T[1000001], P[1001]; 7 8 void make_next() 9 17 } 18 19 int kmp() 20 29 } 30 31 int main() 32
View Code

后话。。。。。。。。。。

事实上，下标从1开始在某些问题上处理边界更好处理

update

#include <cstdio> #include <cstring> #define N 1000001 int n, m; int next[N]; char s1[N], s2[N]; inline void make_next() } inline void kmp() } int main()

　　

上一篇：23-8-7

下一篇：IDEA 常用快捷键

---

模板 kmp