问题 F: #103. 子串查找
题目描述
这是一道模板题。
给定一个字符串 A和一个字符串 B，求 B 在 A 中的出现次数。
A中不同位置出现的 B 可重叠。
输入
输入共两行，分别是字符串 A 和字符串 B。
输出
输出一个整数，表示 B 在 A 中的出现次数。
样例输入
zyzyzyz
zyz
样例输出
3
提示
1≤A,B 的长度 ≤106 ，A 、B 仅包含大小写字母。
简单KMP模板水题。
因为之前写KMP时next数组有两个计算方式，记得时候记混了，导致错了几次。
#include<stdio.h>
#include<string.h>
int next[1010000];
char s1[1010000],s2[1010000];
int main()
{int i,j,k,m,n,a,b;memset(s1,0,sizeof(s1));memset(s2,0,sizeof(s2));while(scanf("%s%s",s1,s2)!=EOF){memset(next,0,sizeof(next));m=strlen(s1);n=strlen(s2);i=1;j=0;while(i<n)//计算next数组{if(s2[i]==s2[j]){// printf("%c %c\n",s1[i],s1[j]);i++;j++;next[i-1]=j;//注意这一点赋值顺序是在i++和j++之前还是之后}else if(j==0&&s2[i]!=s2[j]){// printf("%c %c\n",s1[i],s1[j]);i++;}else if(j>0&&s2[i]!=s2[j]){// printf("%c %c\n",s1[i],s1[j]);j=next[j-1];}}
// for(i=0;i<=n;i++)
// {
// printf("%d ",next[i]);
// }
// printf("\n");i=0;j=0;int f=0;while(i<m)//KMP算法{if(s1[i]==s2[j]){// printf("%c %c i=%d j=%d\n",s1[i],s2[j],i,j);i++;j++;}else if(j==0&&s1[i]!=s2[j]){// printf("%c %c i=%d j=%d\n",s1[i],s2[j],i,j);i++;}else if(j>0&&s1[i]!=s2[j]){// printf("%c %c i=%d j=%d\n",s1[i],s2[j],i,j);j=next[j-1];}if(j==n)//当j==n时表示第二个字符串在第一个字符串中出现一次{// printf("%d\n",i);j=next[j-1];f++;}}printf("%d\n",f);}return 0;
}