字符串匹配算法：KMP
字符串匹配算法：KMP
Knuth–Morris–Pratt（KMP）算法是一种改进的字符串匹配算法，它的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。它的时间复杂度是 O(m+n)。
一般来说，暴力匹配时：
我们在进行每一轮匹配时，总是会重复对 A 进行比较。也就是说，对于 S 中的每个字符，我们都需要从 T 第一个位置重新开始比较，并且 S 前面的 A 越多，浪费的时间也就越多。假设 S 的长度为 m，T 的长度为 n，理论上讲，最坏情况下迭代 m - n + 1 轮，每轮最多进行 n 次比对，一共比较了 次，当 时，渐进时间复杂度为 。
力扣卡片解析→KMP