2
518def 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在下个字节匹配失败之后，为什么不直接从开始匹配，而是要回到上个字节匹配的位置？
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
收藏
如果pattern是cct，待匹配的字符串是xaccct，那么，当pattern匹配到第三个c时，c与t不匹配，是倒回第一个c，还是倒回第二个c？
明白了。
是和自己的前缀相匹配，因为之前的一个字符已经匹配成功了，所以先把前缀移到之前匹配到的位置，这个位置是可能发生成功匹配的最远位置，之后再后移继续匹配。
相当于对自己进行KMP