KMP算法,计算failure function的问题。 财富值77

2016-11-03 14:48发布

def compute_fail(pattern):     fail = [0 for i in range(len(pattern))]     m = len(pattern)     j = 0     i = 1     while i < m:         if pattern[i] == pattern[j]:             fail[i] = j + 1             j += 1             i += 1         elif j > 0:             j = fail[j-1] #这里为什么要回到上个字节匹配的值,而不是直接从0开始。         else:             fail[i] = 0             i += 1     return fail

在下个字节匹配失败之后,为什么不直接从开始匹配,而是要回到上个字节匹配的位置?

2条回答
珞洛 - 这个人很懒,什么都没留下
1楼 · 2016-11-03 15:26.采纳回答

如果pattern是cct,待匹配的字符串是xaccct,那么,当pattern匹配到第三个c时,c与t不匹配,是倒回第一个c,还是倒回第二个c?

明白了。
是和自己的前缀相匹配,因为之前的一个字符已经匹配成功了,所以先把前缀移到之前匹配到的位置,这个位置是可能发生成功匹配的最远位置,之后再后移继续匹配。
相当于对自己进行KMP

一周热门 更多>