鱼C论坛

 找回密码
 立即注册
查看: 5429|回复: 24

[技术交流] 看了几天KMP算法,终于有眉目了!

[复制链接]
发表于 2012-5-16 22:05:35 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
把自己的想法说一说,主要是总结一下书上的内容!
KMP算法是一种改进的模式匹配算法,他到底和传统的模式匹配法有什么区别呢?
例如:
主串A:  a b a b c a b c
模式串Ba b c a c
传统的方法是先用i指向主串A中的第一个元素,j指向B中的的一个元素。若是对应AB中的元素相同则ij分别向后移,直到对应的A[ i ] < >B[ j ],此时回溯指针iji 向前进一步,j = 1)重新开始比较,知道B模式串完全凭匹配为止。
你会发现这样很麻烦,每次不相同的时候就要回溯。KMP算法就解决了这个问题。
如上例,比较到i = 5 j = 7 时:
              i = 7
file:///C:/Users/ADMINI~1.AEF/AppData/Local/Temp/ksohtml/wps_clip_image-27797.png   
a
b
a
b
c
a
b
c
a
c
  
A
file:///C:/Users/ADMINI~1.AEF/AppData/Local/Temp/ksohtml/wps_clip_image-127.png            j = 5
a
b
c
a
c
        B
我们不必回溯指针,利用A[ 6 ] = B[ 1 ] = B[ 4 ]这个特点你可以直接将B串继续向前推进。
直接比较 B [1] A [ 7]。说白了KMP算法就是解决失配时模式串向前推进多少步,即,失配后应与哪一个元素继续比较。上题中,失配前一个元素和第一个元素相同,也就是说,
当我们将B串向前推进3 个单元后直接比较第二个元素B[ 2 ]看是否与A[ 7 ]相同。也就是说当失配前有一个元素和第一个元素相同时我们可以直接比较模式串中的第二个元素。
现在推广到一般:
file:///C:/Users/ADMINI~1.AEF/AppData/Local/Temp/ksohtml/wps_clip_image-1604.png假设主串为'S1 S2 S3.......Sn’ ,模式串为‘P1 P2 P3 ........Pn’当比配过程中,若产生Si< > Pj ,Pj前有k - 1个元素满足 ‘Pj - k + 1........Pj -1’ = P1......Pk-1’(我们希望k是满足此条件的最大值,我的理解是最大限度的模仿上一次的匹配,也就是最大限度利用上次匹配的信息);若有满足此条件的k - 1存在,下次我们就可以直接比较Si Pk 了。我们可以用函数next[ j ] = k来表示失配后应继续比较的字符位置。综上可以定义next函数:
0   j = 1
next[ j ]  =  Max{ k | 1 <  k  < jPj - k + 1........Pj - 1’ = P1......Pk-1}
此集合不为空时
                    1    其他情况
第二个公式非常重要,意思再重复一遍:next[ j ] =  k,意味着在失配处j之前有k -1个元素和模式串最先的k - 1个字符相同。j 处失配我们就直接比较k处。根据next函数看书上的KMP算法不难理解。一直困扰我的是next函数的求法,给定一段模式串如何编程求出next函数呢?
书上说求next函数的问题把模式串既当模式串又当主串,书上还说可以用递推的方法来求next函数。怎么个递推呢?next [ 1 ] = 0不用说了。现在就是知道next[ j ]  =  k,怎么求next[j + 1]next[ j ]  = k的意思我们强调过了:若产生Si< > Pj ,Pj前有k - 1个元素满足 ‘Pj - k + 1........Pj - 1’ = P1......Pk-1’(k 为满足条件的最大值);如图示:
P1      
.........
Pk - 1
Pk
.......
Pj - k +1
............
Pj -1
Pj
Pj +1
   ......
要求next [ j + 1]就有两种情况:
1Pk = Pj 此时Pj + 1之前有k个元素满足和字符串之前的k个元素相同。所以
next [ j +1]  =  k + 1,也就是next[j + 1] = next[ j ] + 1;
2, 现在看Pk< > Pj时,这个时候就应该想到模式匹配的问题书上说“求next函数的问题 把模式串既当模式串又当主串”这句话我们现在这样看,如图:
P1      
.....
Pk - 1
Pk
......
Pj - k +1
....
Pj -1
Pj
Pj +1
   ......
P1      
.......
Pk - 1
Pk
......
Pj - k +1
........
Pj -1
......
现在Pj < > Pk 根据之前所讲,next[ k ] 就应该是下一个和Pj比较的地方,假设next[ k ] = k',
Pk' = Pj此时next[j + 1] = k' + 1;若还此时仍然有Pk' < >Pj,也就是仍然失配,很明显我们必须继续找下一个可能存在Pn= Pj 的地方,当然还是用模式匹配的方法求next[ k ']直到存在
Pnext[ next[ next [ .....]  ] ] = Pj,此时next[j + 1] = next[ next[ next [ .....]  ] ]  + 1;如果不存在 next[ j + 1] = 1,意味着我们必须从第一个开始比较。综上描述可以写出求next函数的伪代码:
void  get_next (SString  T, int next [])
{
i = 1;next[ 1 ] = 0; j = 0;
while(i < T[ 0 ] )
{
if (j == 0 ||  T[ i] = T[ j ])
{i++; j++; next [ i] = j;}
else
j = next[j];
}
}
问题貌似已经解决了,其实不然,上面写的算法还有一个不足。例如模式串为a a a a b时。与主串 a a b a c a a,匹配一下。如图:
a
a
a
b
c
a
a
a
a
a
a
b

i = 4j =4 时失配, 此时右移多少个单元呢?一眼就可以看出来要右移四个单位。
但是具体是怎么做的呢?我们发现此时Pj < > Si,并且Pj = Pk。所以应该直接跳到
P next [k] 处来比较,可是如果P next[ k ] = Pj 呢?我们当然要继续往下找P next[next[...]]
。若最后next[next[...]] = 0,找到第一个还是有P0 = Pj ,所以我们应该把主串中的指针往后移一位继续与P1比较。得到修正next函数的伪代码:
void get_nextval(SString T, int nextval[])
{
i = 1; nextval[ 1 ] = 0; j =0
if (i  < T[ 0 ])
{
while (j == 0 || T == T[j])
{
  i ++;
j ++;
if (T  ! =  T[j])
nextval = j;
else  j =nextval[j];
}
}
}


评分

参与人数 1鱼币 +10 收起 理由
小甲鱼 + 10 插入的时候右上角有个word格式的插入~

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 2012-5-16 22:06:32 | 显示全部楼层
汗死,word里面的格式怎么都没了!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2012-5-16 22:35:25 | 显示全部楼层
我也在学数据结构,KMP看了个大概就混过去了。。。
顶LZ啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 2012-5-16 22:42:36 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2012-5-17 00:06:52 | 显示全部楼层
kmp啊。。好东西就是要顶
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2012-5-18 02:13:07 | 显示全部楼层
:lol我现在也在学数据结构啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2012-5-18 07:59:03 | 显示全部楼层
很高深,还没到这步呢
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2012-5-18 08:09:53 | 显示全部楼层
我在等小甲鱼讲课时候再学数据结构,因为我很菜,就会一点C。:L
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2012-5-18 16:26:20 | 显示全部楼层
我咋觉得跟书上的没啥区别啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 2012-5-18 16:49:28 | 显示全部楼层
紫炎 发表于 2012-5-18 16:26
我咋觉得跟书上的没啥区别啊

书上讲求next函数的时候把模式串即当主串也当模式串,我当时没看懂这句话,想了好久有些明白,总结一下!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2012-5-18 20:56:47 | 显示全部楼层
他用的递归 吧
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2012-5-18 21:30:19 | 显示全部楼层
表述数据结构没学过这东西  看不懂
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2012-6-16 01:05:56 | 显示全部楼层
这是什么哦0.0.
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
头像被屏蔽
发表于 2012-6-20 23:46:26 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2012-11-6 20:10:57 | 显示全部楼层
在学数据结构,在kmp算法卡壳了,蛋疼……思绪凌乱啊,在寻求解决方法
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 2012-11-7 14:01:54 | 显示全部楼层
shisan_ 发表于 2012-11-6 20:10
在学数据结构,在kmp算法卡壳了,蛋疼……思绪凌乱啊,在寻求解决方法

自己多看几遍书吧,我也是看了好久才明白一点的!现在都快忘光了,好久没看数据结构了!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-7-2 11:59:05 | 显示全部楼层
看看老帖,支持下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-7-3 22:11:22 | 显示全部楼层
看看支持下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-7-4 12:47:03 | 显示全部楼层
再看看,以表支持
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-7-4 18:48:16 | 显示全部楼层
再看看,回帖支持支持
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-3-29 17:49

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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