KMP算法

其实KMP算法最重要的是获得next[]数组的值，而next的只代表当字符不匹配时指向子串的指针应该回退到的地方,
他的值就是前缀字符串和后最字符串相等的最大的串的长度
abab前缀子串a;ab;abc;后缀子串b;ab;bab;所以到第2个b最大的相等的前后缀子串是2；

以abcabaa为例子；(下划线为了上下对齐，没有其他用途)
子串： a__b__c__a__b__a__a
next[]: 0__0__0__1__2__1__1
然后把next的值前一个覆盖后一个，第一个补上-1即得到最后的next；
子串： a___b___c__a__b__a__a
next[]: -1__0___0__0__1__2__1

以下是代码：

#include<iostream>
using namespace std;
//普通的BF算法
int BF(char*s, char*sub, int len1, int len2)
{ if(s==NULL||sub==NULL||len2>len1) { return -1; } int i=0; int j=0; while(i<len1&&j<len2) { if(s[i]==sub[j]) { i++; j++; } else { i=i-j+1; j=0; } } if(j==len2) { return i-len2; } else { return -1; }

}
//GETNEXT
void GetNext(int arr[], char*sub , int len2)
{ if(arr==NULL) { return ; } int i=0; int j=0; for(i=0;i<len2;++i) { j=i+1; if(sub[j]==sub[arr[i]])//如果相等，说明j前面的字符也匹配 { arr[j] = arr[i]+1; } else { if(sub[j]==sub[0]) { arr[j]=1; } else { arr[j] = 0; } } } //向后移 for(i=len2-2; i>=0; --i) { arr[i+1] = arr[i]; } arr[0] = -1;
}
//O(m+n)
int KMP(int arr[], char*s,char*sub,int len1,int len2)
{ if(arr==NULL||s==NULL||s==NULL||len2>len1) { return -1; } GetNext(arr,sub,len2); int i=0; int j=0; while(i<len1&&j<len2) { if(j==-1 || sub[j]==s[i]) { i++; j++; } else { j = arr[j]; } } if(len2==j) { return i-len2; } else { return -1; }
}


int main()
{ char*s="abcabcdfg"; char*sub = "abcab"; int len1 = strlen(s); int len2 = strlen(sub); int *arr = (int*)malloc(sizeof(int)*len2); memset(arr, 0, sizeof(int)*len2); //int res = BF(s,sub,len1,len2); //cout<<res<<endl; int res= KMP(arr,s,sub,len1,len2); cout<<res<<endl; free(arr); return 0;
}
  

 

  
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
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
  
94
  
95
  
96
  
97
  
98
  
99
  
100
  
101
  
102
  
103
  
104
  
105
  
106
  
107
  
108
  
109
  
110
  
111
  
112
  
113
  
114
  
115
  
116
  
117
 

文章来源: blog.csdn.net，作者：IM-STONE，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/doubleintfloat/article/details/52705120