kmp算法

MP（Knuth-Morris-Pratt）算法是一种字符串快速匹配算法，核心思想是：

利用已经匹配过的信息，把模式串自己和自己对比，提前算出一张“跳步表”（next 数组），主串的指针永不回溯，一次扫描完成匹配。

时间复杂度：

• 预处理 O(m)
• 匹配 O(n)总 O(n+m)，远优于暴力 O(n·m)。

一、暴力 vs KMP（直观例子）

主串 S = ababcabcacbab
模式 P = abcac

暴力做法：
每次失配就把 P 往后挪 1 位，主串指针要回溯，最坏 15×5=75 次比较。

KMP 做法：
失配时只把 P 按 next 数组右滑，主串指针不动，共 19 次比较就找到答案。

def kmp_search(s, p):

   n, m = len(s), len(p)

   nxt = build_next(p)

   j = 0               # 当前在模式串的位置

   for i in range(n):  # i 只增不减，永不回溯

       while j and s[i] != p[j]:

           j = nxt[j-1]  # 失配，按 next 滑 P

       if s[i] == p[j]:

           j += 1

       if j == m:        # 完全匹配

           return i - m + 1

   return -1