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条回答

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

一周热门 更多>