发布网友
共1个回答
热心网友
/*感觉百度上的答友遇到这种题就没几个回答的了哈哈!
这道题可以采用最笨的方法,即从第一个字符挨个比较
但是这里采用KMP算法统计一个字符串在另一个字符串出现的次数,在时间和空间上开销更小
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int counter=0; //定义计数器,统计一个字符串在另一个字符串中出现的频率
void getnext(char* p,int* next) //计算next数组,表示下一个跳转的位置,详细你去看看kmp算法吧~
{
int len=strlen(p);
int k=0,i;
next[0]=0;
for(i=1;i<len;i++)
{
while(k>0&&p[i]!=p[k])
k=next[k];
if(p[i]==p[k])
k++;
next[i]=k;
}
}
void kmp(char* s,char* p) //kmp算法主调函数
{
int lens=strlen(s);
int lenp=strlen(p);
int* next=(int*)malloc((lenp+10)*sizeof(int)); //动态分配数组用于存储next数组
getnext(p,next);
int k=0;
for(int i=0;i<lens;i++) //对字符串进行匹配跳转操作
{
while(k>0&&p[k]!=s[i])
k=next[k];
if(p[k]==s[i])
k++;
if(k==lenp)
{
counter++; //匹配成功counter++
k=next[k-1];
}
}
free(next);
}
int main()
{
char a[1000],b[1000];
gets(a);
gets(b);
kmp(a,b); //计算字符串b在a中出现的次数
printf("出现的次数:%d\n",counter);
return 0;
}