hdu 1686 Oulipo （kmp）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1686

题目大意：寻找子链在母链中出现的次数。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 int next[10010],sum,lens,lenc;
 6 char str[10010],ch[1000010];
 7 
 8 int get_next()
 9 {
10     int i=0,j=-1;
11     next[0]=-1;
12     while (i<strlen(str))
13     {
14         if (j==-1||str[i]==str[j])
15         {
16             i++;j++;
17             next[i]=j;
18         }
19         else
20         j=next[j];
21     }
22 }
23 
24 void kmp()
25 {
26     int i=0,j=0;
27     lens=strlen(str);
28     lenc=strlen(ch);
29     while (i<lenc&&j<lens)
30     {
31         if (j==-1||ch[i]==str[j])
32         {
33             i++;
34             j++;
35             //next[i]=j;
36         }
37         else
38         j=next[j];
39         if (j>=lens)
40         {
41             sum++;
42             j=next[j];
43         }
44     }
45 }
46 
47 int main ()
48 {
49     int t;
50     scanf("%d",&t);
51     while (t--)
52     {
53         getchar();
54         scanf("%s",str);
55         //getchar();
56         scanf("%s",ch);
57         //gets(str);
58         //getchar();
59         //gets(str);
60         get_next();
61         sum=0;
62         kmp();
63         printf ("%d
",sum);
64     }
65     return 0;
66 }