冬天¤不回来
海风轻轻吹过我的脸庞 阳光温柔的洒在我身上 海鸥自由的飞在天空中像 快乐的徘徊在游乐场 白云在偷看彩虹的模样 海洋总为那船长指方向 海浪抚摸著沙滩的衣裳 我也每天都为他换上新装 找到方向 揭开迷茫 学着坚强 努力去闯!
posts - 20,  comments - 90,  trackbacks - 0
昨天在文章中提到了修正,没有给出解释.今天进行补充.让我们先来看看我的好友写的吧!
/////////////////////////////////////////////////////////////////////////////
程序没有使用一个数组来保存未修正时的NEXT值 而直接用J来充当这个功能 但是J是由NEXT(已修正)得来的 那么有没有可能J得不到正确的值?
这个问题最先是我自己想的 后来验证了一下 J一定能够得到正确的值
下面我们来分析一下
下标                         0  1  2  3  4  5  6  7  8  9 10 11 1213
目标串                     0  1  0  0  1  0  1  0  1  0  0   0   0  1
j(未修正的next)       -1 0  0  1  1  2  3  2  3  2  3   4   1  1
修正了的next          -1 0 -1  1  0 -1  3 -1 3 -1  0  4   1   0

让我们看看但模式串比较到了12位的时候(下标为11)
next[11] = 4; next[4] = 0; j|4 = 1...
这时候next[4]拿到的并不是正确的J值!!!
这会导致什么?会导致略过一个比较 即p[11]与p[1]的比较被略过!直接比较了p[11]与p[0]!
是否可以略过这个比较?!
答案是肯定的.
根据逻辑推理 如果p[11]与p[4]不等 而p[4] = p[1]那么p[11]与p[1]一定不等 所以可以略过
这样说似乎很牵强 我们再回想一下NEXT数组的意义 即当我们比较到i位时不等 应该由哪一位重新开始比较 而实际上 这个过程相当于在 7-11的这个串中查找0-3!所以根据NEXT数组的意义 我们也可以知道 这里并不会导致错误 由于被略去的比较一定不需比较 因此 J始终可以得到正确的未修正的NEXT值!
////////////////////////引用自室友 <KMP算法浅析>http://www.cppblog.com/sicheng/archive/2006/10/10/13537.html////////////

上面的例子很经典! 这里我也写点容易的,给和我一样理解能力不强的笨苯 OHOH!

看这个例子:
                     p = "aaaba"  , t = "aaabbaaaaaaaba"

                                        a  a  a  b  b  a  a  a  a  a  a  a  b  a
 
                                        a  a  a  b  a                         (第一次)

                                            a  a  a  b  a                     (第二次)

                                                              ...............

                                                                           a  a  a  b  a (成功匹配)

      1.为什么要进行修正?  我们把next数组比喻成第一次比较.  在第一次比较中,比较失败的是"第"4个字符a,这表明前4个字符是成功的!" 而p中的b的前3个字符并没有出现b",也就是说在下一趟比较中,至少应该将p向右移动4个字符;因此得到了未修正的next值=4 .
      2.而实际上,p的头个字符与最后一个字符是一样的(a).也就是说如果按照上面所说的4进行移位,再从p的头个字符开始比较同样肯定是不等的(将会出现下面的情况)
                                        a  a  a  b  b  a  a  a  a  a  a  a  b  a
 
                                        a  a  a  b  a                         (第一次)

                                                       a  a  a  b  a          (这次第一个字符a  和 第一次比较最后一个字符是一样的,因此移4位肯定也不等)

得出结论是:应该将p向右移动五位. 再从p的头个字符进行比较.

     3.所以说对于某个字符串,在算出next[i]的值后,不一定会得到"最快速的移动位数).拿上面的例子说,第2次其实移4和5位其实最后都能比较出正确答案.但移5位最好(得到休整值最好).

  怎样计算修正的值,就去看我同学的连接吧,写得很清楚,不知道上面我是否写清楚了(嘿嘿),我尽力了!!!!!




posted on 2006-10-11 18:52 冬天¤不回来 阅读(4171) 评论(2)  编辑 收藏 引用

FeedBack:
# re: KMP算法详解(NEXT数组修正的补充)
2007-01-05 19:00 | 冬天¤不回来
好像写的不太清楚
  回复  更多评论
  
# re: KMP算法详解(NEXT数组修正的补充)
2008-08-10 19:51 | 郭勍
不是很明白。  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


QQ:41696402

<2006年10月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(3)

随笔档案

文章档案

Programming

最新随笔

搜索

  •  

积分与排名

  • 积分 - 37430
  • 排名 - 532

最新评论

阅读排行榜

评论排行榜