python - 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

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

解决方案

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

这篇关于python - KMP算法，计算failure function的问题。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！