字符串匹配之KMP，C++实现

文字介绍KMP我就不讲了，相信大家看了不少别的文章也没看懂，我肯定也不能用文字表达清楚。

最好的办法就是看严老师的视频，讲的很清晰。

请百度 KMP 严蔚敏；

在这里我用C++实现一下；

 1 #include <iostream>   
 2 #include <string>   
 3 #include<vector>
 4 using namespace std;
 5 class KMP
 6 {
 7 public:
 8     KMP(string s_,string t_) //构造函数，主串和模式串的接口
 9     {
10         s=s_;t=t_;
11     }  
12     void get_nextval();//得到nextval的值
13     void visit_nextval(vector<int> );//nextval接口
14     int index_kmp(int);//索引匹配
15 protected:
16     string s,t;
17     vector<int> nextval;
18 };
19 void KMP::get_nextval()  
20 {  
21     int i=1,j=0;   
22     nextval[1]=0;  
23     while(i<(int)t.size()-1)  
24     {  
25         if(j==0||t[i]==t[j])  
26         {  
27             ++i;  
28             ++j;  
29             if(t[i]!=t[j])  
30                 nextval[i]=j;  
31             else  
32                 nextval[i]=nextval[j];  
33         }  
34         else  
35             j=nextval[j]; 
36 
37     }  
38 }  
39 int KMP::index_kmp(int pos)  
40 {  
41     int i=pos;  
42     int j=1;  
43     while(i<=(int)s.size()-1&&j<=(int)t.size()-1)  
44     {  
45         if(j==0||s[i]==t[j])  
46         {  
47             ++i;  
48             ++j;  
49         }  
50         else  
51             j=nextval[j];
52     }  
53     if(j>(int)t.size()-1)  
54         return i-((int)t.size()-1);  
55     else  
56         return 0;
57 }  
58 void KMP::visit_nextval(vector<int> next )
59 {
60     nextval=next;
61 }
62 int main()  
63 {  
64         string temp,s,t;  
65         s.push_back('*');  
66         t.push_back('*');  //没有使用s[0]和t[0],随意使用一个字符进行填充（不要用字母）
67         cout<<"输入主串:";  
68         getline(cin,temp);  //用getline函数输入串
69         s+=temp;
70         cout<<"输入模式串:";  
71         getline(cin,temp);  
72         t+=temp;
73    　　 KMP teststring(s,t);
74    　　 vector<int> nextval;
75    　　 nextval.assign(t.size()+1,0);
76     　　teststring.visit_nextval(nextval);  
77    　　 teststring.get_nextval();  
78        cout<<teststring.index_kmp(1)<<endl;  
79 }