KMP算法

hdu1686http://acm.hdu.edu.cn/showproblem.php?pid=1686

可以重叠

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<vector>
 8 #include<stack>
 9 #include<queue>
10 #define lson l, m, rt<<1
11 #define rson m+1, r, rt<<1|1
12 #define IO ios::sync_with_stdio(false);cin.tie(0);
13 #define INF 1e9
14 #define MAXN 500010
15 const int MOD=1e9+7;
16 typedef long long ll;
17 using namespace std;
18 int n, Next[10010], cnt;
19 char s[1000010], p[10010];
20 void cal_Next()
21 {
22     int k = -1, len = strlen(p);
23     Next[0] = -1;
24     for(int i = 1; i < len; i++){
25         while(k > -1&&p[k+1] != p[i]){
26             k = Next[k];//核心 
27         }
28         if(p[k+1] == p[i])
29             k = k+1;
30         Next[i] = k; 
31     }
32     /*for(int i = 0; i < len; i++){
33         cout << Next[i] << " ";
34     }*/
35 }
36 void KMP()
37 {
38     int k = -1, slen = strlen(s), plen = strlen(p);
39     cal_Next();
40     for(int i = 0; i < slen; i++){
41         while(k > -1&&p[k+1] != s[i]){
42             k = Next[k];
43         }
44         if(p[k+1] == s[i])
45             k = k+1;
46         if(k == plen-1){
47             k = Next[k];//可以重叠 
48             cnt++; 
49         }
50     }
51 } 
52 int main()
53 {
54     IO;
55     cin >> n;
56     while(n--){
57         cnt=0;
58         cin >> p >> s;
59         KMP();
60         cout << cnt << endl;
61     }
62     return 0;
63 }

hdu2087http://acm.hdu.edu.cn/showproblem.php?pid=2087

不能重叠

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<vector>
 8 #include<stack>
 9 #include<queue>
10 #define lson l, m, rt<<1
11 #define rson m+1, r, rt<<1|1
12 #define IO ios::sync_with_stdio(false);cin.tie(0);
13 #define INF 1e9
14 #define MAXN 500010
15 const int MOD=1e9+7;
16 typedef long long ll;
17 using namespace std;
18 int n, Next[10010], cnt;
19 char s[1000010], p[10010];
20 void cal_Next()
21 {
22     int k = -1, len = strlen(p);
23     Next[0] = -1;
24     for(int i = 1; i < len; i++){
25         while(k > -1&&p[k+1] != p[i]){
26             k = Next[k];//核心 
27         }
28         if(p[k+1] == p[i])
29             k = k+1;
30         Next[i] = k; 
31     }
32     /*for(int i = 0; i < len; i++){
33         cout << Next[i] << " ";
34     }*/
35 }
36 void KMP()
37 {
38     int k = -1, slen = strlen(s), plen = strlen(p);
39     cal_Next();
40     for(int i = 0; i < slen; i++){
41         while(k > -1&&p[k+1] != s[i]){
42             k = Next[k];
43         }
44         if(p[k+1] == s[i])
45             k = k+1;
46         if(k == plen-1){
47             k = -1;//不重叠 
48             cnt++; 
49         }
50     }
51 } 
52 int main()
53 {
54     IO;
55     while(cin >> s){
56         if(s[0] == '#')
57             break;
58         cin >> p;
59         cnt=0;
60         KMP();
61         cout << cnt << endl;
62     }
63     return 0;
64 }