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?
一周热门 更多>