#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
char a[10000],b[10000];
int pre[10000];
void prepare(char *t){
int j=pre[1]=0;
int m=strlen(t+1);
for (int i=2;i<=m;i++){
while (j&&t[j+1]!=t[i]) j=pre[j];
pre[i]=(t[j+1]==t[i])? ++j : j ;
}
}
int KMP(char *a,char *b){
int j=0;
int cnt=0;
int n=strlen(a+1);
int m=strlen(b+1);
for (int i=1;i<=n;i++){
while (j&&b[j+1]!=a[i]) j=pre[j];
if (b[j+1]==a[i]) j++;
if (j==m){
cnt++;
j=pre[j];
}
}
return cnt;
}
int main(){
freopen("text1.txt","r",stdin);
freopen("result.txt","w",stdout);
scanf("%s",b+1);
prepare(b);
int ans=0;
freopen("text2.txt","r",stdin);
while (scanf("%s",a+1)!=EOF) ans+=KMP(a,b);
if (ans) printf("Words existed in text2 %d times\n",ans);
else puts("Not found!");
fclose(stdout);
system("notepad.exe result.txt");
fclose(stdin);
return 0;
}
建议用KMP算法,具体算法可以看matrix67的blog。
http://www.matrix67.com/blog/archives/115