首页 >社区问答列表 >KMP算法,计算failure function的问题。

KMP算法,计算failure function的问题。

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

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

  • 代言
  • 代言    2016-11-09 14:34:332楼

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

    +0添加回复

  • 回复
  • 三叔
  • 三叔    2016-11-09 14:34:181楼

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

    +0添加回复

  • 回复