彻底理解字符串匹配KMP算法

文章预览

今天简单聊聊字符串匹配kmp算法。 字符串匹配是计算机科学中非常基础的操作，给定两个字符串a和b，我们需要判断字符串a是否包含字符串b。 像你我这样的普通程序员能想到的最简单方法是这样的，用字符串b不断去匹配每个主串中的子串。 假设给定这样两个字符串： 首先从主串的第一个位置和子串的第一个位置去匹配，我们发现A和B不相同： 因此主串指针后移一位，子串重新从最第一个字符开始匹配。 这时我们发现A和C不同，因此匹配失败。 主串指针回退到第三个字符，子串重新从第一个字符开始匹配。 此时B和A又不同，重复上述过程。 这次成功找到多个相同的字符，但最后一个字符匹配失败： 按照我们的算法，主串指针需要回退到第5个字符重新匹配。 这就是你我这种肉体凡胎能想到的算法，时间复杂度是O(mn)，效率低下的原因当然是主串 ………………………………