KMP

骇客king

#include <stdio.h>
#include <string.h>
typedef char* String;
void get_next(String a,int *next)
{        int i=0,j=1;
        next[1]=0;
        while(j<a[0])
        {
                if(i==0||a[i]==a[j])
                {
                        i++;
                        j++;
                        if(a[i]!=a[j])
                        {
                                next[j]=i;
                        }
                        else
                        {
                                next[j]=next[i];
                        }               
                }
                else
                {
                        i=next[i];
                }
        }
}
void init_kmp(String a,String b)
{
        int next[255];
        int i=1,j=1;
        get_next(b,next);
        while(i<=a[0])
        {
                while(i<=a[0]&&j<=b[0])
                {
                        if(j==0||a[i]==b[j])
                        {
                                i++;
                                j++;
                        }
                        else
                        {
                                j=next[j];
                        }
               
                }
                if(j>b[0])
                {
                        printf("%d\n",i-b[0]);
                }
                else
                {
                        printf("%d",0);
                }
                j=0;
        }       
}
void main()
{
        char a[255]=" BBC ABCDABCDABDAB ABCDABCDABDEABCDABD";
        char b[255]=" ABCDABD";
        a[0]=(int)(strlen(a))-1;
        b[0]=(int)(strlen(b))-1;
        init_kmp(a,b);
}

大侠帮忙看看，哪里需要改进的地方，虽然写出来了，但是貌似有个别点还是有点模糊，其中有的还是参考别人的写出来的。

leonardzzy

骇客king 发表于 2015-8-24 21:49
返回1,7 不对吗？应该就是返回7和1啊
你要是想返回2和8 就在,i-b[0] 加1就行了

我刚才调试了一下  我知道原因了 我之前觉得是1 3 7

leonardzzy

楼主 我想问问你 i-b[0]是什么意思啊？

骇客king

i为当前主串配比成功的位置，减去模式串的总长度，就是模式串在主串中的位置了，可以再加+1，就得出第一个匹配的位置，b[0]就是模式串的长度了。
为什么这么问呢？

leonardzzy

如果a="ababaaaba"
b="aba"
输出为什么是1和7呢？

骇客king

leonardzzy 发表于 2015-8-24 17:43
如果a="ababaaaba"
b="aba"
输出为什么是1和7呢？

我没上机 现在手机看的  串的第一个字符要填写串长度  不知道你填了吗 如果填了 我明天看看哪里有问题 你能帮忙看看哪有问题吗

骇客king

骇客king 发表于 2015-8-24 21:21
我没上机 现在手机看的  串的第一个字符要填写串长度  不知道你填了吗 如果填了 我明天看看哪里有问题 你 ...

返回1,7 不对吗？应该就是返回7和1啊
你要是想返回2和8 就在,i-b[0] 加1就行了

1和7是对整个数组说话的，因为最前边是存放的是串的长度，要占一个位置的，你可以手动加上1，或心理加一个，哈哈

骇客king

应该有更好的方法，不需要第一个元素放串长度，用结构是不是有点浪费，还有如果要动态串长度，是不是就得用结构了，封装到一个dll里，以后调用就方便了。

430524tian

建议看看数据结构里的 KMP。

狼之道

不错不错，我原理懂了，但写起来也有点模糊

y290176346

感谢楼主的奉献 我要鱼币

y290176346

我 是来得鱼币的

time.c

没有问题！