KMP 算法+Python 实现

KMP 算法

字符串匹配有很多算法可以实现，Knuth-Morris-Pratt 算法（简称KMP）是最常用的之一，时间复杂度为 O(m+n)，其中 m 为模式串的长度，n 为目标串的长度。
具体的 KMP 算法还是比较复杂的，推荐阅读参考的两篇文章。

Python 代码

class KMP(object):
    """KMP algorithm."""
    def kmp(self, s, pattern):
        """KMP string matching function.
        
        Args:
            s: str, target string.
            pattern: str, pattern string.
            
        Returns:
            index: int, the starting matching index of s (-1 if cannot match).
        """
        __next = self.get_next(pattern)
        i = j = 0  # 分别为 s 和 pattern 的指针
        while i < len(s) and j < len(pattern):
            if j == -1 or s[i] == pattern[j]:
                # j 为 -1 是由 j = __next[j] 回溯产生的，即回溯到了 pattern 开头。
                # 说明此处没有公共前缀与后缀，两个指针同时后移，相当于从 pattern 的头部开始重新匹配。
                i += 1
                j += 1
            else:
                j = __next[j]
        if j == len(pattern):
            return i - j
        return -1
    
    def get_next(self, pattern):
        """Get 'next' array for a pattern string."""
        # 注：得到 next 数组的方法相当于 pattern 自身与自身的匹配算法
        # 不同的是，因为 next[0] = -1，所以相当于 pattern 与 pattern[1:] 匹配
        __next = [0] * len(pattern)
        __next[0] = -1
        i = 1  # pattern[1:] 的指针
        j = 0  # pattern 的指针
        while i < len(pattern) - 1:  # pattern[1:] 长度只有 len(pattern) - 1
            if j == -1 or pattern[i] == pattern[j]:
                i += 1
                j += 1
                __next[i] = j
            else:
                j = __next[j]
        return __next


if __name__ == "__main__":
    s = "ababababca"
    p = "abababca"
    # print("Next:", KMP().get_next(p))
    print(KMP().kmp(s, p))

参考

https://www.zhihu.com/question/21923021/answer/281346746
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html