KMP算法
详解
https://blog.csdn.net/weixin_52622200/article/details/110563434
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| void getNext(string p, int *next){
int lenp = p.length();
int j = 0, k = -1;
next[0] = -1;
while(j<lenp-1){
if(k==-1||p[j]==p[k]){
j++; k++;
if(p[j]==p[k]){
next[j] = next[k];
}else{
next[j] = k;
}
}else{
k = next[k];
}
}
}
int KMP(string t, string p, int *next){
int lent = t.length();
int lenp = p.length();
int i = 0, j = 0;
while(i<lent&&j<lenp){
if(j==-1||t[i]==p[j]){
i++; j++;
}else{
j = next[j];
}
}
if(j==lenp) return i-j;
return -1;
}
int strStr(string haystack, string needle) {
int lent = haystack.length();
int lenp = needle.length();
if(lenp==0) return 0;
int next[lenp];
getNext(needle, next);
return KMP(haystack, needle, next);
}
|