kmp模板

有两种next求法

 1 #include <iostream>
 2 #include <string>
 3 #include <cstring>
 4 using namespace std;
 5 const int maxn=1e6+5;
 6 char S[maxn],T[maxn];
 7 int Next[maxn],nextval[maxn];//next冲突不要用
 8 
 9 /*void GetNext()//根据定义求法(稍慢)
10 {
11     int i=1,j=0;//j=0;会进i++保证此部分Next[2]开始填
12     int len=strlen(T+1);
13     next[1]=0;
14 
15     while(i<len)//i<len!因为i==时已经填完!
16     {
17         if(j==0 || T[i]==T[j])
18         {
19             i++;
20             j++;
21             Next[i]=j;
22         }
23         else j=Next[j];
24     }
25 }*/
26 
27 void GetNextval()//在定义基础上,考虑一种特殊情况修改优化求法,如
28 {                          //S:aaabaaaab
29     int i=1,j=0;//j=0;     //T:aaaab
30     int len=strlen(T+1);
31     nextval[1]=0;
32 
33     while(i<len)
34     {
35         if(j==0 || T[i]==T[j])
36         {
37             i++;
38             j++;
39             if(T[i]!=T[j]) nextval[i]=j;
40             else nextval[i]=nextval[j];
41         }
42         else j=nextval[j];
43     }
44 }
45 
46 int Kmp(int pos)//从第pos个位置开始往后,一般是1往后
47 {
48     int i=pos,j=1;//j=1;不会进i++保证从第一个字符开始比较
49     int len1=strlen(S+1),len2=strlen(T+1);
50 
51     while(i<=len1 && j<=len2)//i==时还需要判断,>才退出!
52     {
53         if(j==0 || S[i]==T[j])
54         {
55             i++;
56             j++;
57         }
58         else j=nextval[j];//i不用回溯,只有j回溯！
59     }
60 
61     if(j>len2) return i-len2;
62     return 0;
63 }
64 
65 int main()
66 {
67     ios::sync_with_stdio(false); cin.tie(0);
68     cin>>S+1;
69     cin>>T+1;
70 
71     GetNextval();
72     int ans=Kmp(1);
73     if(ans) cout<<ans<<endl;
74     else cout<<"0"<<endl;
75 
76     return 0;
77 }

模板题，hduoj2087剪花布条

数据比较水，可以Bf暴力匹配，Kmp匹配，string查找函数水过

  1 #include <iostream>
  2 #include <string>
  3 #include <cstring>
  4 using namespace std;
  5 const int maxn=1e6+5;
  6 char S[maxn],T[maxn];
  7 int nextval[maxn];
  8 
  9 void GetNextval()
 10 {
 11     int i=1,j=0;
 12     int len=strlen(T+1);
 13     nextval[1]=0;
 14 
 15     while(i<len)//i<len!
 16     {
 17         if(j==0 || T[i]==T[j])
 18         {
 19             i++;
 20             j++;
 21             if(T[i]!=T[j]) nextval[i]=j;
 22             else nextval[i]=nextval[j];
 23         }
 24         else j=nextval[j];
 25     }
 26 }
 27 int Kmp(int pos)
 28 {
 29     int i=pos,j=1;
 30     int len1=strlen(S+1),len2=strlen(T+1);
 31 
 32     while(i<=len1 && j<=len2)
 33     {
 34         if(j==0 || S[i]==T[j])
 35         {
 36             i++;
 37             j++;
 38         }
 39         else j=nextval[j];
 40     }
 41 
 42     if(j>len2) return i-len2;
 43     return 0;
 44 }
 45 
 46 /*int Bf(int pos)//暴力匹配
 47 {
 48     int i=pos,j=1;
 49     int len1=strlen(S+1),len2=strlen(T+1);
 50     while(i<=len1 && j<=len2)
 51     {
 52         if(S[i]==T[j])
 53         {
 54             i++;
 55             j++;
 56         }
 57         else
 58         {
 59             i=i-j+2;
 60             j=1;
 61         }
 62     }
 63 
 64     if(j>len2) return i-len2;
 65     return 0;
 66 }*/
 67 
 68 int main()
 69 {
 70     ios::sync_with_stdio(false); cin.tie(0);
 71 
 72     while(cin>>S+1)
 73     {
 74         if(S[1]=='#') break;
 75 
 76         cin>>T+1;
 77         int len1=strlen(S+1),len2=strlen(T+1);
 78         if(len1<len2)
 79         {
 80             cout<<'0'<<endl;
 81             continue;
 82         }
 83         int cnt=0;
 84         //memset(nextval,0,sizeof(nextval))
 85         GetNextval();
 86         for(int i=1;i<=len1;)
 87         {
 88             int ans=Kmp(i);
 89             if(ans)
 90             {
 91                 i=ans+len2;
 92                 cnt++;
 93 
 94             }
 95             else break;
 96         }
 97 
 98         cout<<cnt<<endl;
 99     }
100 
101     return 0;
102 }

完。