KMP

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 char text[1010],pattern[1001];
 5 int next[1001];
 6 void getNext()
 7 {
 8     int k=-1,j=0;
 9     int lenp=strlen(pattern);
10     next[0]=-1;///不要忘了给此处赋值
11     while(j<lenp){
12         if(k==-1||pattern[k]==pattern[j]){
13             ++j;++k;
14             next[j]=k;
15         }
16         else{
17             k=next[k];///此处千万不要写反了
18         }
19     }
20 }
21 
22 int kmp()
23 {
24     int i=0,j=0,c=0;
25     int lent=strlen(text),lenp=strlen(pattern);
26     getNext();///不要忘了这一步
27     while(i<lent){
28         if(j==-1||text[i]==pattern[j]){
29             ++i;++j;
30         }
31         else
32         {
33             j=next[j];
34         }
35         if(j==lenp){
36             j=0;
37             c++;
38         }
39     }
40     return c;
41 }
42 
43 int main()
44 {
45     while(~scanf("%s",text)&&strcmp(text,"#")!=0){
46         scanf("%s",pattern);
47         int ans=kmp();
48         printf("%d\n",ans);
49     }
50     return 0;
51 }

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 ///不知道为什么，这里不能加using namespace std;
 5 const int maxn=2000001;
 6 int text[maxn],pattern[maxn];
 7 int next[maxn];
 8 int N,M;
 9 void getNext(){
10     int j=0,k=-1;
11     next[0]=-1;
12     while(j<M){
13         if(k == -1||pattern[j]==pattern[k])
14         {
15             j++;
16             k++;
17             next[j]=k;
18         }
19         else{
20             k=next[k];
21         }
22     }
23 }
24 
25 int kmp()
26 {
27     int i=0,j=0;
28     while(i<N&&j<M)
29     {
30         if(j==-1||text[i]==pattern[j]){
31             i++;j++;
32         }
33         else
34             j=next[j];
35     }
36     if(j>=M){
37         return i-M+1;
38     }
39     return -1;
40 }
41 int main()
42 {
43     int T;
44     scanf("%d",&T);
45     while(T--)
46     {
47         scanf("%d%d",&N,&M);
48         for(int i=0;i<N;i++)
49             scanf("%d",&text[i]);
50         for(int i=0;i<M;i++)
51             scanf("%d",&pattern[i]);
52         getNext();
53         int ans=kmp();
54         printf("%d\n",ans);
55         /*for(int i=0;i<M;i++)
56             printf("%d\n",next[i]);*/
57     }
58     return 0;
59 }