KMP算法用于实现字符串匹配问题。例如查找某个字符串是否是s的子串。普通方法是从s字符串的开头开始一次比较。时间复杂度O(n*m)。KMP该是该方法的优化方法。KMP算法的核心思想,就是每次如果字符串没有匹配成功,不是从头开始重新查找,而是从一个特定的合理位置开始继续查找,减少了查找次数那我们应该如何去找到这个特定的合理位置呢,这就是KMP算法的关键,引入一个前缀表的概念。