S001 【模板】从前缀函数到KMP应用 字符串匹配 字符串周期

这篇博客为总结的解题流程和模板，如果想要算法具体的原理和数学证明的话请参考：Prefix function. Knuth–Morris–Pratt algorithm
最长相等真前后缀

最长相等前后缀也被称为 Border ，KMP算法就利用了其性质来进行匹配优化。

• 前缀：从字符串第一个字符开始的子串。
  
• 后缀：以字符串最后一个字符结束的子串。
  
• 真：长度严格小于原字符串长度。
  

求法（ \(O(n^2)\) ）：

1. def border(s):
2.     n = len(s)
3.     L = 0
4.     for i in range(1, n):  # 长度为 i 上限为 n-1 确保为真前后缀
5.         if s[:i] == s[n-i:n]:
6.             L = i
7.     return L

复制代码

还有更加高效的算法，可以优化到 \(O(n)\) 。正是这个优化产生了 KMP 算法。
前缀函数

在 KMP 中的前缀函数的到数组 \(\pi\) ，其中 \(\pi\) 表示字符串的前缀 \(t[0\dots i]\) 中，最长的相等真前后缀的长度。
如果使用暴力枚举每个子串进行一次 border 函数的话时间复杂度是 \(O(n^3)\)

1. b = []
2. for i in range(len(s)):
3.     b.append(border(s[:i + 1]))

复制代码

通过递推可以在 \(O(n)\) 时间内求出前缀数组 \(\pi\)

• 假设我们正在计算 \(\pi\) ，并且已知 \(\pi[i-1]=j\) 。
  
• 这意味着 \(t[0\dots j-1]\) 是 \(t[0\dots i-1]\) 的最长相等前后缀。
  
• 情况A：如果 \(t==t[j]\) ，那么 \(\pi = j+1\) 。
  
• 情况B：如果 \(t \ne t[j]\) ，我们需要一个更短的相等前后缀。于是我们可以让 \(j=\pi[j-1]\) ，然后重复 \(t\) 和 \(t[j]\) 的比较过程，直到匹配或 \(j\) 降为 \(0\) 。
  

具体代码为

1. def get_pi(s):
2.     n = len(s)
3.     pi = [0] * n
5.     for i in range(1, n):
6.         j = pi[i - 1]  # 取前一个的位置的pi
8.         while j > 0 and s[i] != s[j]:  # 情况B
9.             j = pi[j - 1]
10.         if s[i] == s[j]:  # 情况A
11.             j += 1
12.         pi[i] = j
14.     return pi

复制代码

应用

模式串匹配

已知模式串 \(t\) 和匹配串 \(s\) ，在预处理完模式串的 \(\pi\) 数组后可以通过双指针匹配。

• 指针 \(i\) ：始终在 \(s\) 上向右移动，不回退。
  
• 指针 \(j\) ：在 \(t\) 上移动，如果匹配 j++ 如果失配 \(j\) 根据 \(\pi\) 数组向左跳，跳到一个可以让前面部分继续匹配的位置。
  

这个根据 \(\pi\) 数组向左跳的过程可以理解成下面这句有名名的话：

一个人能走的多远不在于他在顺境时能走的多快，而在于他在逆境时多久能找到曾经的自己。

1. m, n = len(t), len(s)
2. pi = get_pi(t)
4. j = 0  # 模式串指针
5. for i in range(n):  # 文本串指针永不回退
6.     while j > 0 and s[i] != t[j]:
7.         j = pi[j - 1]
9.     if s[i] == t[j]:
10.         j += 1
12.     if j == m:  # 匹配成功
13.         # 位置为 i - j + 1 0-based
14.         j = pi[j - 1]  # 继续匹配可能重叠的下一处

复制代码

求字符串周期

先利用预处理的 \(\pi\) 数组求出所有的 Border ，再根据这些 Border 就可以构造出所有的周期串了。
求字符串所有周期

由于 \(\pi\) 数组记录了最长 Border ，而次长的 Border 可能通过 \(\pi[\pi[n-1]-1]\) 递归求得，因此我们可以不断回跳，求出所有的 Border 后，周期就是 n - Border。

1. n = len(s)
2. pi = get_pi(s)
4. b = []
5. k = pi[n - 1]
6. while k:
7.     b.append(n - k)
8.     k = pi[k - 1]
9. b.append(n)
11. print(*b)

复制代码

不要忘记了 \(s\) 自身也是周期，然后每个周期串就是 s[:b] 。
完全循环

在 \(\pi[n-1]>0\) 基础上，当它的最小正周期 \(n-\pi[n-1]\) 可以被总长度 \(n\) 整除时，存在完全循环。

1. n = len(s)
2. pi = get_pi(s)
4. k = n - pi[n - 1]
5. print("YES" if pi[n - 1] > 0 and n % k == 0 else "NO")

复制代码

例题

1753 String Matching - CSES  模式串匹配模版
1732 Finding Borders - CSES  求出字符串所有 Border
1733 Finding Periods CSES  求出所有的周期大小
459. 重复的子字符串 - 力扣  判断是否存在完全循环

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！