鱼C论坛

 找回密码
 立即注册
查看: 4640|回复: 13

KMP

[复制链接]
发表于 2015-8-24 16:29:57 | 显示全部楼层 |阅读模式
10鱼币
#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);
}

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

最佳答案

查看完整内容

我刚才调试了一下 我知道原因了 我之前觉得是1 3 7
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-8-24 16:29:58 | 显示全部楼层
骇客king 发表于 2015-8-24 21:49
返回1,7 不对吗?应该就是返回7和1啊
你要是想返回2和8 就在,i-b[0] 加1就行了

我刚才调试了一下  我知道原因了 我之前觉得是1 3 7
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-8-24 17:28:27 | 显示全部楼层
楼主 我想问问你 i-b[0]是什么意思啊?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2015-8-24 17:40:32 | 显示全部楼层
i为当前主串配比成功的位置,减去模式串的总长度,就是模式串在主串中的位置了,可以再加+1,就得出第一个匹配的位置,b[0]就是模式串的长度了。
为什么这么问呢?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-8-24 17:43:15 | 显示全部楼层
如果a="ababaaaba"
b="aba"
输出为什么是1和7呢?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2015-8-24 21:21:47 | 显示全部楼层
leonardzzy 发表于 2015-8-24 17:43
如果a="ababaaaba"
b="aba"
输出为什么是1和7呢?

我没上机 现在手机看的  串的第一个字符要填写串长度  不知道你填了吗 如果填了 我明天看看哪里有问题 你能帮忙看看哪有问题吗
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2015-8-24 21:49:28 | 显示全部楼层
本帖最后由 骇客king 于 2015-8-24 21:52 编辑
骇客king 发表于 2015-8-24 21:21
我没上机 现在手机看的  串的第一个字符要填写串长度  不知道你填了吗 如果填了 我明天看看哪里有问题 你 ...


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

1和7是对整个数组说话的,因为最前边是存放的是串的长度,要占一个位置的,你可以手动加上1,或心理加一个,哈哈
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2015-8-25 12:44:08 | 显示全部楼层
应该有更好的方法,不需要第一个元素放串长度,用结构是不是有点浪费,还有如果要动态串长度,是不是就得用结构了,封装到一个dll里,以后调用就方便了。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-8-26 14:22:13 | 显示全部楼层
建议看看数据结构里的 KMP。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-8-31 21:23:30 | 显示全部楼层
不错不错,我原理懂了,但写起来也有点模糊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-9-3 23:24:17 | 显示全部楼层
感谢楼主的奉献 我要鱼币
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-9-16 15:15:40 | 显示全部楼层
我 是来得鱼币的
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2015-12-6 14:34:22 | 显示全部楼层
没有问题!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

头像被屏蔽
发表于 2015-12-23 20:29:43 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-23 13:23

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表