由于有限自動(dòng)機(jī)方法與KMP算法類似，并且有限自動(dòng)機(jī)方法在預(yù)處理上的時(shí)間復(fù)雜度比KMP方法高，所以在本文的討論中，暫時(shí)不討論有限自動(dòng)機(jī)方法，主要是考慮KMP算法。
KMP算法是一個(gè)非常有名的字符串匹配算法，其由Knuth,Morris和Pratt一起提出來的，預(yù)處理時(shí)間為O(m),其中m為匹配字符串的長度，匹配時(shí)間為O(n)，其中n為需要匹配的字符串的長度。
核心算法如下：
//預(yù)處理部分
int pi[m];
pi[0]=0;
int k = 0;
for(int i=1;i<m;i++)
{
while((k>0)&&(p[i]!=p[k])
k=pi[k];
if(p[i]==p[k])
k++;
pi[i]=k;
}
//匹配部分
int k=0;
for(int i=0;i<n;i++)
{
while((k>0)&&(p[k]!=t[i]))
k=pi[k];
if(p[k]==t[i])
k++;
if(k==m)
{
//輸出結(jié)果，從(i+1-m)開始已經(jīng)匹配
k=pi[m-1];//開始下一個(gè)匹配
}
}
具體的可運(yùn)行的實(shí)現(xiàn)代碼為：
1 #include <iostream>
2 #include <string>
3
4 using namespace std;
5
6 int main(int argc,char* argv[])
7 {
8 char *t=NULL,*p=NULL;
9 int *pi=NULL;
10 string text,pattern;
11
12 while(1)
13 {
14 cin>>text>>pattern;
15 int n = text.length();
16 int m = pattern.length();
17
18 //t= new char[n+1];
19 //p= new char[m+1];
20 t= new char[n];
21 p= new char[m];
22 pi = new int[m];
23
24 //strcpy(t,text.c_str());
25 //strcpy(p,pattern.c_str());
26 memcpy(t,text.data(),n);
27 memcpy(p,pattern.data(),m);
28
29 //calculate the PI array
30 int q = 0;
31 pi[0]=0;
32
33 for(int i=1;i<m;i++)
34 {
35 while((q>0)&&(p[q]!=p[i]))
36 {
37 q=pi[q];
38 }
39
40 if(p[q]==p[i])
41 q++;
42
43 pi[i]=q;
44 }
45
46 //use the KMP matching algorithm
47 q = 0;
48 for(int i=0;i<n;i++)
49 {
50 while((q>0)&&(p[q]!=t[i]))
51 {
52 q = pi[q];
53 }
54
55 if(p[q]==t[i])
56 q++;
57
58 if(q==m)
59 {
60 cout<<((i+1)-m)<<endl;
61 q = pi[m-1];
62 }
63 }
64
65 delete[] t;
66 delete[] p;
67 delete[] pi;
68 }
69
70 system("pause");
71 return 0;
72 }
73