用C来写KMP的时候，懂了就忘了，理解不深刻，果然还是python更直观。
KMP的next数组是关键，就几行，看懂了就能看着字符串直接写出next数组了，nice!
def getNext(pattern, next): j = 0 plen = len(pattern) next.append(0) for i in range(1, plen): while j > 0 and pattern[j] != pattern[i]: j = next[j-1] if pattern[i] == pattern[j]: j = j + 1 next.append(j)之后就是跟主串匹配了
今日知道了KMP的next数组的另一个直观的算法。 匹配前缀和后缀的办法： http://kb.cnblogs.com/page/176818/ "前缀"指除了最后一个字符以外，一个字符串的全部头部组合； "后缀"指除了第一个字符以外，一个字符串的全部尾部组合。 "部分匹配"的实质是，有时候，字符串头部和尾部会有重复。比如，"ABCDAB"之中有两个"AB"，那么它的"部分匹配值"就是2（"AB"的长度）。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），就可以来到第二个"AB"的位置。 def pattern_next(s): prefix = [s[:i+1] for i in range(len(s)-1)] suffix = [s[i+1:] for i in range(len(s)-1)] l = list(set(prefix) & set(suffix)) return len(l)
