[hdu2087]剪花布条(KMP)

题意：求存在模式串个数，不可重复。

解题关键：模板题。整理模板用。重复和不可重复的区别在下面已标出。主要是j的变化。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #include<iostream>
 7 #define N 1000002
 8 using namespace std;
 9 typedef long long ll;
10 int Next[N];
11 char s[N],t[N];
12 int slen,tlen;
13 int n,m;
14 int num=0,num1=0,num2=0;
15 void getNext(){
16     int i=0,j=-1;
17     Next[0]=-1;
18     while(i<tlen){
19         if(j==-1||t[i]==t[j]) Next[++i]=++j;
20         else j=Next[j];
21     }
22 } 
23 int kmp_index(){
24     int i=0,j=0;
25     while(i<slen&&j<tlen){
26         if(j==-1||s[i]==t[j]) i++,j++;
27         else j=Next[j];
28     }
29     if(j==tlen) return i-j;
30     else return -1;
31 }
32 
33 int kmp_count(){
34     int ans=0,i=0,j=0;
35     for(i=0;i<slen;i++){
36         while(j>0&&s[i]!=t[j]) j=Next[j];
37         if(s[i]==t[j]) j++;
38         if(j==tlen){
39             ans++;
40             j=0;//j=Next[j];
41         }
42     }
43     return ans;
44 }
45 
46 int main(){
47     while(scanf("%s",s)&&s[0]!='#'){
48         scanf("%s",t);
49         slen=strlen(s);
50         tlen=strlen(t);
51         getNext();
52         int ans=kmp_count();
53         printf("%d
",ans);
54     }
55     return 0;
56 }