昨天在文章中提到了修正,没有给出解释.今天进行补充.让我们先来看看我的好友写的吧!
/////////////////////////////////////////////////////////////////////////////
程序没有使用一个数组来保存未修正时的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
冬天¤不回来 阅读(4295)
评论(2) 编辑 收藏 引用