| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3249 人关注过本帖
标题:[收集]]关于KMP算法!
只看楼主 加入收藏
zjl138
Rank: 1
等 级:新手上路
威 望:1
帖 子:788
专家分:0
注 册:2007-11-12
收藏
 问题点数:0 回复次数:23 
[收集]]关于KMP算法!
关于KMP.老实说,我是看了至少四遍才基本理解它的整个推导过程,真是菜也.
第一遍连看下去的耐心都没有,第二遍看着看着干脆去吃饭了,直到第三遍,第四遍,做了练习之后,情况才有所好转...呵呵..

个人理解KMP的主要思想就是 : 模式串在跟主串匹配的时候主串的指针不回溯。至于它的推导过程,很多书上都有详细过程,我就不多说了,这里给出我写的一个代码,代码有注释,应该能看明白吧!也请大家把自已写过的关于模式匹配的代码共享出来.让我对这个算法的应用有更多的了解,谢谢!!!
my code:



/*****************************************************************
** HighlightCodeV3.0 software by yzfy(雨中飞燕) [url]http://[/url] **
*****************************************************************/
#include<iostream>      
#define MAXSIZE 32   
using namespace std;   
//定义结构体   
struct stack_ch   
{   
   
char ch[MAXSIZE];   
    int Length;   
};   
   
//求next函数值   
   
void GetNext(stack_ch ch,int next[MAXSIZE])   
{   
   
int i=1,j=0;   
    next[1]=0;   
    while (i<ch.Length)   
    {   
        
if (j==0 || ch.ch[i]==ch.ch[j])   
        {   
            
i++;   
            j++;   
            next[i]=j;   
        }   
        
else   
            
j=next[j];   
    }   
}
//Get_next   
   
//输入字符串   
void Enter_stack(stack_ch &ch,int next[MAXSIZE])   
{   
        
char data;   
        ch.Length=0;   
        cin>>data;   
        while (data!='*')   
        {   
        
ch.ch[++ch.Length]=data;   
        cin>>data;   
        }   
}   
   
//将模式串和主串进行匹配操作,返回模式串在主串S第pos个字符之后可匹配的位置   
   
int Index_KMP(stack_ch S,stack_ch T,int pos,int next[MAXSIZE])   
{   
        
//利用模式串T的next函数求T在主串S中第pos个字符之后的位置,T非空且1<=pos<=S.Length   
        
int i=pos,j=1;   
        while (i<=S.Length && j<=T.Length)   //对两串扫描
        
{   
        
if (j==0 || S.ch[i]==T.ch[j])    //对应字符匹配
        
{   
            
i++;   
            j++;   
        }   
        
else   
            
j=next[j];   
        }   
        
if (j>T.Length)     
        return (i-T.Length);        //匹配成功
        
else   
        return
0;                 //匹配失败
} //Index_KMP   
   
int main(void)   
{   
        
stack_ch S,T;   
        int next[MAXSIZE],pos,pos2;   
        cout<<"输入主串:(end by '*')"<<endl;   
   
        //输入主串   
   
    Enter_stack(S,next);   
        cout<<"输入模式串:(end by '*')"<<endl;   
   
        //输入模式串   
   
    Enter_stack(T,next);   
        GetNext(T,next);   
        cout<<"输入pos的值(1<=pos<=S.Length)S是主串:"<<endl;   
   
        //输入pos值   
        
cin>>pos;   
        pos2=Index_KMP(S,T,pos,next);   
   
        //输出所求的位置值   
        
cout<<"The position is:"<<pos2<<endl;   
        system("pause");
        return 0;
}


[ 本帖最后由 zjl138 于 2008-5-24 18:09 编辑 ]
搜索更多相关主题的帖子: KMP 算法 收集 模式 代码 
2008-05-24 12:25
lnhaing
Rank: 1
等 级:新手上路
帖 子:111
专家分:0
注 册:2008-1-30
收藏
得分:0 
好久没来了论坛!
最近也在学习这些 很是 恶心 算法!
学习了!

我来自偶然! bitter C
2008-05-24 12:36
雨中飞燕
Rank: 3Rank: 3
等 级:禁止访问
威 望:8
帖 子:2200
专家分:0
注 册:2007-8-9
收藏
得分:0 
呃。。。这代码。。。。

[color=white]
2008-05-24 14:23
zjl138
Rank: 1
等 级:新手上路
威 望:1
帖 子:788
专家分:0
注 册:2007-11-12
收藏
得分:0 
原帖由 雨中飞燕 于 2008-5-24 14:23 发表 [url=http://bbs.bccn.net/redirect.php?goto=findpost&pid=1282622&ptid=215672]呃。。。这代码。。。。

 

怎么了?
还有个问题,好像你那个高亮软件在论坛升级后失灵了..

[ 本帖最后由 zjl138 于 2008-5-24 14:30 编辑 ]

i like linux...
2008-05-24 14:29
雨中飞燕
Rank: 3Rank: 3
等 级:禁止访问
威 望:8
帖 子:2200
专家分:0
注 册:2007-8-9
收藏
得分:0 
我知道,我换了新版本,还能用的,你只要再去那个帖子重新下载一下
不过附件还能不能用不清楚,偶一会去更新试试

[color=white]
2008-05-24 14:30
zjl138
Rank: 1
等 级:新手上路
威 望:1
帖 子:788
专家分:0
注 册:2007-11-12
收藏
得分:0 
好,谢谢!

i like linux...
2008-05-24 14:32
菜鸟选手
Rank: 1
等 级:新手上路
帖 子:132
专家分:0
注 册:2008-5-5
收藏
得分:0 
整了一天才弄懂 KMP算法的路过..~

算法学习群57909089
2008-05-24 16:40
sunkaidong
Rank: 4
来 自:南京师范大学
等 级:贵宾
威 望:12
帖 子:4496
专家分:141
注 册:2006-12-28
收藏
得分:0 
void GetNext(stack_ch ch,int next[MAXSIZE])   
{   
    int i=1,j=0;   
    next[1]=0;   
    while (i<ch.Length)   
    {   
        if (j==0 || ch.ch[i]==ch.ch[j])   
        {   
            i++;   
            j++;   
            next[i]=j;   
        }   
        else   
            j=next[j];   
    }   
}//Get_next  
精华在这里。我兄弟的帖子我帮顶下。。呵呵
kmp在模拟栈。。靠next数组里面的下标和内容差一实现。。
设计一个模式串abcabc
第一次:
a!=b
j==0,所以执行i++,j++,next[2]=1;i==2,j==1;
第二次:
由于条件都不成立,所以执行else语句
j=next[j];==>j=next[j]=0;
这里可以理解为从末尾向前找出现相同字符位置。。
下面体现比较明显,当执行到abca得时候c与a不等一直倒推到a==a即ch.ch[i]==ch.ch[j]
i==4,j==1;执行i++,j++,next[5]=2;即当目标串出现在这里匹配失败的时候要把模式串的下标移到2。下面就好理解了。。。我只是大概看了一下。。希望和朋友们一起提高。。

学习需要安静。。海盗要重新来过。。
2008-05-24 22:13
zhuwei168
Rank: 1
来 自:东软信息学院
等 级:新手上路
帖 子:180
专家分:0
注 册:2008-2-13
收藏
得分:0 
怎么给我感觉这个代码好像是两个数组比较
相同的就取出来
那回事呢??
高手解释一下哈
谢谢

做一个自由的人,飞到蔚蓝的天空里。
2008-05-25 10:59
sunkaidong
Rank: 4
来 自:南京师范大学
等 级:贵宾
威 望:12
帖 子:4496
专家分:141
注 册:2006-12-28
收藏
得分:0 
这个是在目标字符串中查找模式字符串的很好的方法,效率很高,在目标字符串中指针不需要回溯,关键已经说了,建一个数组模拟栈的过程。

学习需要安静。。海盗要重新来过。。
2008-05-25 11:04
快速回复:[收集]]关于KMP算法!
数据加载中...
 
   



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

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