...求一个c语言程序 希望能用简单常见的语句 跪谢!

发布网友

我来回答

共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;
}