| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 319 人关注过本帖
标题:KMP算法 关于求next[]
只看楼主 加入收藏
木头lbj
Rank: 7Rank: 7Rank: 7
来 自:黄山
等 级:黑侠
威 望:1
帖 子:269
专家分:527
注 册:2010-11-6
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:2 
KMP算法 关于求next[]
对kmp算法真心弄不明白。。。下面是我自己写的算法的实现,不能成功运行。。。。求指教。。。关键是在于对next[]的引用上。。。写的很乱。。。
程序代码:
#include <stdio.h>
#define M 100

int GetNext(char *t,int next[]);
int StrIndex_KMP(char *s,char *t);

int main()
{
    char s[M];
    char t[M];
    printf("请输入目标串:\n");
    gets(s);
    printf("请输入模式串:\n");
    gets(t);
    StrIndex_KMP(s,t);
}

int GetNext(char *t,int next[])
{
    int i = 0, j = 0;
    next[1] = 0;
    while(i < strlen(t))
    {
        if(j == 0 || t[i] == t[j])
        {
            ++ i;
            ++ j;
            next[i] = j;
            return next[i];
        }
        else
        j = next[j];
        return j;
    }
}

int StrIndex_KMP(char *s,char *t)
{
    int i = 2,j = 1;
    int next[M];
    while(i <= strlen(s) && j <= strlen(t))
        if(j == 0 || s[i] == t[j])
            {
            i ++;
            j ++;
            }
            else
            j = GetNext(t,next);
            if(j > strlen(t))
            printf("匹配成功!位置为%d\n",i - strlen(t)+1);
            else
            printf("匹配失败!\n");
   
    return 0;
}
2011-05-29 17:20
lz1091914999
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:四川
等 级:贵宾
威 望:37
帖 子:2011
专家分:5959
注 册:2010-11-1
收藏
得分:5 
什么是KMP?

My life is brilliant
2011-05-29 17:33
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:15 
KMP是一种高效的字符串模式匹配算法  字串回溯法 在匹配过程中 如果遇到不匹配

会不断的移动字串到主串 的当前起始匹配字符的下一个字符继续匹配

这是很费时的  KMP在此基础上做了改进 也就是求出字串中每个元素的next[j]值

这样在遇到不匹配的时候 只需要移动字串的第next[j]个字符与主串的第i个对齐

然后继续匹配

                                         
===========深入<----------------->浅出============
2011-05-29 20:53
快速回复:KMP算法 关于求next[]
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.049801 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved