kmp模板

 1 #include <cstdlib>
 2 #include <cctype>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <cmath>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <string>
 9 #include <iostream>
10 #include <sstream>
11 #include <map>
12 #include <set>
13 #include <queue>
14 #include <stack>
15 #include <fstream>
16 #include <numeric>
17 #include <iomanip>
18 #include <bitset>
19 #include <list>
20 #include <stdexcept>
21 #include <functional>
22 #include <utility>
23 #include <ctime>
24 
25 
26 #define PB push_back
27 #define MP make_pair
28 #define FOR1(n) for(int i=0;i<(n);++i)
29 #define FOR2(l,h) for(int i=(l);i<=(h);++i)
30 #define FOR3(h,l) for(int i=(h);i>=(l);--i)
31 
32 using namespace std;
33 typedef vector<int> VI;
34 typedef vector<string> VS;
35 typedef vector<double> VD;
36 typedef long long LL;
37 typedef pair<int,int> PII;
38 
39 #define PI acos((double)-1)
40 #define E exp(double(1))
41 const int K=1e7+9;
42 string s,p;
43 int n,nt[K];
44 void kmp_next(void)
45 {
46     memset(nt,0,sizeof(nt));
47     for(int i=1,j=0;i<p.length();i++)
48     {
49         while(j>0 && p[i]!=p[j])
50             j=nt[j-1];
51         if(p[i]==p[j])j++;
52         nt[i]=j;
53     }
54 }
55 void kmp(void)
56 {
57     n=0;
58     for(int i=0,j=0;i<s.length();i++)
59     {
60         while(j>0 && s[i]!=p[j])
61             j=nt[j-1];
62         if(s[i]==p[j]) j++;
63         if(j==p.length()) n++,j=0;//匹配成功
64     }
65 }
66 int main(void)
67 {
68     cin>>s>>p;
69     kmp_next();
70     kmp();
71     cout<<n<<endl;
72     return 0;
73 }

  1 /*
  2 pku3461(Oulipo), hdu1711(Number Sequence)
  3 这个模板 字符串是从0开始的
  4 Next数组是从1开始的
  5 
  6 
  7 */
  8 #include <iostream>
  9 #include <cstring>
 10 using namespace std;
 11 
 12 const int N = 1000002;
 13 int next[N];
 14 char S[N], T[N];
 15 int slen, tlen;
 16 
 17 void getNext()
 18 {
 19     int j, k;
 20     j = 0; k = -1; next[0] = -1;
 21     while(j < tlen)
 22         if(k == -1 || T[j] == T[k])
 23             next[++j] = ++k;
 24         else
 25             k = next[k];
 26 
 27 }
 28 /*
 29 返回模式串T在主串S中首次出现的位置
 30 返回的位置是从0开始的。
 31 */
 32 int KMP_Index()
 33 {
 34     int i = 0, j = 0;
 35     getNext();
 36 
 37     while(i < slen && j < tlen)
 38     {
 39         if(j == -1 || S[i] == T[j])
 40         {
 41             i++; j++;
 42         }
 43         else
 44             j = next[j];
 45     }
 46     if(j == tlen)
 47         return i - tlen;
 48     else
 49         return -1;
 50 }
 51 /*
 52 返回模式串在主串S中出现的次数
 53 */
 54 int KMP_Count()
 55 {
 56     int ans = 0;
 57     int i, j = 0;
 58 
 59     if(slen == 1 && tlen == 1)
 60     {
 61         if(S[0] == T[0])
 62             return 1;
 63         else
 64             return 0;
 65     }
 66     getNext();
 67     for(i = 0; i < slen; i++)
 68     {
 69         while(j > 0 && S[i] != T[j])
 70             j = next[j];
 71         if(S[i] == T[j])
 72             j++;
 73         if(j == tlen)
 74         {
 75             ans++;
 76             j = next[j];
 77         }
 78     }
 79     return ans;
 80 }
 81 int main()
 82 {
 83     
 84     int TT;
 85     int i, cc;
 86     cin>>TT;
 87     while(TT--)
 88     {
 89         cin>>S>>T;
 90         slen = strlen(S);
 91         tlen = strlen(T);
 92         cout<<"模式串T在主串S中首次出现的位置是: "<<KMP_Index()<<endl;
 93         cout<<"模式串T在主串S中出现的次数为: "<<KMP_Count()<<endl;
 94     }
 95     return 0;
 96 }
 97 /*
 98 test case
 99 aaaaaa a
100 abcd d
101 aabaa b
102 */