KMP POJ 3461 Oulipo

 1 /*
 2     题意：问一个串在另一个串出现的次数(可重复)
 3     KMP：模板题
 4 */
 5 /************************************************
 6 * Author        :Running_Time
 7 * Created Time  :2015-8-9 19:45:40
 8 * File Name     :POJ_3461.cpp
 9  ************************************************/
10 
11 #include <cstdio>
12 #include <algorithm>
13 #include <iostream>
14 #include <sstream>
15 #include <cstring>
16 #include <cmath>
17 #include <string>
18 #include <vector>
19 #include <queue>
20 #include <deque>
21 #include <stack>
22 #include <list>
23 #include <map>
24 #include <set>
25 #include <bitset>
26 #include <cstdlib>
27 #include <ctime>
28 using namespace std;
29 
30 #define lson l, mid, rt << 1
31 #define rson mid + 1, r, rt << 1 | 1
32 typedef long long ll;
33 const int MAXN = 1e6 + 10;
34 const int INF = 0x3f3f3f3f;
35 const int MOD = 1e9 + 7;
36 int nex[MAXN];
37 char s[MAXN], t[MAXN];
38 
39 void get_nex(int lm)    {
40     int i = 0, j = -1;   nex[0] = -1;
41     while (i < lm)  {
42         if (j == -1 || t[j] == t[i])    {
43             j++;    i++;    nex[i] = j;
44         }
45         else    j = nex[j];
46     }
47 }
48 
49 int KMP(void)   {
50     int ln = strlen (s);    int lm = strlen (t);
51     get_nex (lm);
52     int i = 0, j = 0;   int ans = 0;
53     while (i < ln)  {
54         while (j != -1 && t[j] != s[i]) j = nex[j];
55         j++;    i++;
56         if (j >= lm) {
57             ans++;  j = nex[j];
58         }
59     }
60     return ans;  
61 }
62 
63 int main(void)    {     //POJ 3461 Oulipo
64     int T;  scanf ("%d", &T);
65     while (T--)   {
66         scanf ("%s%s", t, s); 
67         printf ("%d
", KMP ());
68     }
69 
70     return 0;
71 }

 1 /*
 2     题目链接：http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?id=4194
 3      给你两个字符串A，B，请输出B字符串在A字符串中出现了几次(不可重复)
 4 */
 5 /************************************************
 6 * Author        :Running_Time
 7 * Created Time  :2015-8-9 19:45:40
 8 * File Name     :ZSTU_4194.cpp
 9  ************************************************/
10 
11 #include <cstdio>
12 #include <algorithm>
13 #include <iostream>
14 #include <sstream>
15 #include <cstring>
16 #include <cmath>
17 #include <string>
18 #include <vector>
19 #include <queue>
20 #include <deque>
21 #include <stack>
22 #include <list>
23 #include <map>
24 #include <set>
25 #include <bitset>
26 #include <cstdlib>
27 #include <ctime>
28 using namespace std;
29 
30 #define lson l, mid, rt << 1
31 #define rson mid + 1, r, rt << 1 | 1
32 typedef long long ll;
33 const int MAXN = 1e6 + 10;
34 const int INF = 0x3f3f3f3f;
35 const int MOD = 1e9 + 7;
36 int nex[MAXN];
37 char s[MAXN], t[MAXN];
38 
39 void get_nex(int lm)    {
40     int i = 0, j = -1;   nex[0] = -1;
41     while (i < lm)  {
42         if (j == -1 || t[j] == t[i])    {
43             i++;    j++;    nex[i] = j;
44         }
45         else    j = nex[j];
46     }
47 }
48 
49 int KMP(void)   {
50     int ln = strlen (s);
51     int lm = strlen (t);
52     get_nex (lm);
53     int i = 0, j = 0;   int ans = 0;
54     while (i < ln)  {
55         while (j != -1 && s[i] != t[j]) j = nex[j];
56         i++;    j++;
57         if (j == lm) {
58             ans++;  j = 0;      //改动这里就是重新匹配
59         }
60     }
61     return ans;  
62 }
63 
64 int main(void)    {
65     while (scanf ("%s%s", s, t) == 2)   {
66         printf ("%d
", KMP ());
67     }
68 
69     return 0;
70 }
71 
72 不可重复的匹配

不可重复的匹配

编译人生，运行世界！