※ [本文转录自 C_and_CPP 看板 #1GHXQS8y ] 作者: honoYang (......) 看板: C_and_CPP 标题: [问题] KMP字串比对 时间: Tue Sep 4 22:56:25 2012 不好意思 因为有一个一直想不通的地方 所以来请教各位 我想借用一下这个连结的说明 http://w.csie.org/~b99902112/NTUcourse/Chapter8-String.pdf 在这个PDF档的第3页有说明KMP的演算法 而且我也参考了一本资料结构的书籍 但是一直不懂为什麽第3页里说的 （2） T[i+1]≠T[π[i]+1]：这时候就较麻烦一点，但你仔细观察後会发现，既然T[i+1] ≠T[π[i]+1]，那下一个可能的匹配位置一定是T[π[π[i]+1] 为什麽T[i+1]≠T[π[i]+1]时 下一个匹配的位置一定是T[π[π[i]+1] 这个关联性怎麽产生的 我实做了例子试验的确是正确的 但自己无法合理解释这件事 谢谢大家 -- 请大家在2012年军阀大选时 务必投我一票 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 114.43.240.32

※ 发信站: 批踢踢实业坊(ptt.cc) ※ 转录者: honoYang (114.43.240.32), 时间: 09/04/2012 23:37:39