KMP

得到NEXT数组

理论

我们先来看一个例子：

abcaabc

将这个当成模式串，当我们用这个模式串去匹配文本串的时候，我们首先有一种很暴力的做法：

就是每次匹配失败的时候重新开始匹配，但这样有很多重复。

那么我们是不是可以想一种办法，减少这种重复呢。

先看一个表格

j	i	模式串	next
-1	0		next[0]=-1
0	1	a	next[1]=0
-1	1
0	2	ab	next[2]=0
-1	2
0	3	abc	next[3]=0
1	4	abca	next[4]=1
0	4
1	5	abcaa	next[5]=1
2	6	abcaab	next[6]=2
3	7	abcaabc	next[7]=3

通过上面这个表格我们是不是有所发现：

1、next[i]=j (当j！=-1&&i！=0时满足)

2、i 就表示模式串的长度（当然你要用模式串长度-1也行，详见下面的表格，代码就不贴了，留给你自己发挥了）

3、next[0]=-1 （这是为了方便回溯，方便创建next数组）

j	i	模式串	next
-1	0	a	next[0]=-1
0	1	ab	next[1]=0
-1	1
0	2	abc	next[2]=0
-1	2
0	3	abca	next[3]=0
1	4	abcaa	next[4]=1
0	4
1	5	abcaab	next[5]=1
2	6	abcaabc	next[6]=2

代码

void getNEXT() {    int i = 0, j = NEXT[0] =-1;    while (i

在文本串中找到第一个模式串的位置

int FirstKmp() {    int i = 0, j = 0;    while (i < a.size()) {        if (j == -1 || a[i] == Find[j]) {            i++, j++;            if (j == Find.size()) {                return i - j;            }        }        else j = NEXT[j];    }    return -1;}//在a中找到第一个Find的位置

查找文本串中有多少模式串

可以重叠的

int ManyKmp() {    int i = 0, j = 0,ans=0;    while (i < a.size()) {        if (j == -1 || a[i] == Find[j]) {            i++, j++;            if (j == Find.size()) {                ans++;                j = NEXT[j];            }        }        else j = NEXT[j];       }    return ans;} //在a中找几个可以重叠的Find

不可以重叠的

int ManyKMP() {    int i = 0, j = 0, ans = 0;    while (i < a.size()) {        if (j == -1 || a[i] == Find[j]) {            i++, j++;            if (j == Find.size()) {                ans++;                j = 0;            }        }        else j = NEXT[j];    }    return ans;}//在a中找几个不可以重叠的Find