题意:
给定两个串S 和 T,求S中最多不重叠的包含了多少个T串.
分析:
不重叠的话,就是在正常的KMP基础上,匹配到T的末尾的时候,j要回到0.
#include<bits/stdc++.h>using namespace std;
const int maxn = 1111;
char s[maxn],t[maxn];
int f[maxn];
int n,m,last,cnt;void getfail()
{f[0]=f[1]=0;for(int i=1;i<m;i++){int j=f[i];while(j && t[i]!=t[j])j=f[j];f[i+1]=t[i]==t[j]?j+1:0;}
}void kmp()
{n=strlen(s),m=strlen(t);getfail();int j=0;for(int i=0;i<n;i++){while(j && s[i]!=t[j])j=f[j];if(s[i]==t[j])j++;if(j==m){cnt++;j=0;///p从头开始匹配去。正常操作是不从头的}}
}int main()
{while(scanf("%s",s)){if(strcmp(s,"#")==0){break;}scanf("%s",t);cnt=0;kmp();cout<<cnt<<endl;}
}