[python刷题模板] 前缀函数/next数组/kmp算法

• • 一、 算法&数据结构
  • • 1. 描述
    • 2. 复杂度分析
    • 3. 常见应用
    • 4. 常用优化
  • 二、 模板代码
  • • 1. 裸前缀函数
    • 2. 树上kmp
    • 3. 裸kmp
  • 三、其他
  • 四、更多例题
  • 五、参考链接

一、 算法&数据结构

1. 描述

前缀函数和next数组基本上是一个东西，但储存的内容不同。
他们是kmp算法的基础。但真的不太好理解，以及不好写，背不过。
前缀函数π(i)可以在O(n)的时间计算出来数组内每个前缀的前缀函数。

• 参考 oiwiki前缀函数与 KMP 算法
• kmp还可以结合字典树搞ac自动机，待施工。
• 前缀函数π[i]代表的前缀s[:i+1]和后缀s[-i:]相同的情况下，是前缀长度。
  • 简单来说 pi[i] 就是，子串 s[0… i] 最长的相等的真前缀与真后缀的长度。
• next数组是指模式串在i位置匹配失败后，应该向前跳到哪个位置开始继续匹配。

2. 复杂度分析

1. 预处理O(n)
2. 查询O(n)

3. 常见应用

1. 字符串查询。

4. 常用优化

1. 从意义上来说，前缀函数值得是前后缀相同的长度；next数组是匹配失败后模式串指针j要去的位置。

• 因此kmp搜索用next数组写法简单点(参考模板代码3)；但找前后缀用前缀函数更直观（模板代码1）。

二、 模板代码

1. 裸前缀函数

例题: 4808. 构造字符串
这题暴力能过，但还是前缀函数nb。

# Problem: 构造字符串
# Contest: AcWing
# URL: https://www.acwing.com/problem/content/4811/
# Memory Limit: 256 MB
# Time Limit: 1000 msimport sys
import bisect
import random
import io, os
from bisect import *
from collections import *
from contextlib import redirect_stdout
from itertools import *
from array import *
from functools import lru_cache
from types import GeneratorType
from heapq import *
from math import sqrt, gcd, infif sys.version >= '3.8':  # ACW没有combfrom math import combRI = lambda: map(int, sys.stdin.buffer.readline().split())
RS = lambda: map(bytes.decode, sys.stdin.buffer.readline().strip().split())
RILST = lambda: list(RI())
DEBUG = lambda *x: sys.stderr.write(f'{str(x)}\n')MOD = 10 ** 9 + 7def prefix_function(s):"""计算s的前缀函数"""n = len(s)pi = [0] * nfor i in range(1, n):j = pi[i - 1]while j > 0 and s[i] != s[j]:j = pi[j - 1]if s[i] == s[j]:j += 1pi[i] = jreturn pi
#       ms
def solve():n, k = RI()t, = RS()mx = prefix_function(t)[-1]if mx == 0:return print(t * k)suf = t[mx:]print(t + suf * (k - 1))if __name__ == '__main__':solve()

2. 树上kmp

链接: 1367. 二叉树中的链表

试了下树上kmp是负优化，但可能是数据问题。

class Solution:def isSubPath(self, head: ListNode, root: TreeNode) -> bool:path = []while head:path.append(head.val)head = head.nextn = len(path)def get_next(p):n = len(p)nxt = [0]*nnxt[0] = -1j,k=0,-1while j < n-1:if k == -1 or p[j] == p[k]:j+=1k+=1if p[j] == p[k]:nxt[j] = nxt[k]else:nxt[j] = k else:k = nxt[k]return nxtnxt = get_next(path)# print(nxt)def dfs_kmp(tree, j):if j == n:return Trueif not tree:return Falseif j == -1 or tree.val == path[j]:return dfs_kmp(tree.left,j+1) or dfs_kmp(tree.right,j+1)else:return dfs_kmp(tree,nxt[j]) 

3. 裸kmp

链接: 28. 找出字符串中第一个匹配项的下标

class Solution:def strStr(self, haystack: str, needle: str) -> int:m,n = len(haystack),len(needle)# def get_next(p):#     n = len(p)#     nxt = [-1] * n#     j, k = 0, -1#     while j < n - 1:#         if k == -1 or p[j] == p[k]:#             j += 1#             k += 1#             if p[j] == p[k]:#                 nxt[j] = nxt[k]#             else:#                 nxt[j] = k#         else:#             k = nxt[k]#     return nxt# nxt = get_next(needle)# print(nxt)# i = j = 0        # while i < m and j < n:#     if j == -1 or haystack[i] == needle[j]:#         i += 1#         j += 1#     else:#         j = nxt[j]# if j == n:#     return i - j # return -1def prefix_function(s):"""计算s的前缀函数"""n = len(s)pi = [0] * nfor i in range(1, n):j = pi[i - 1]while j > 0 and s[i] != s[j]:j = pi[j - 1]if s[i] == s[j]:j += 1pi[i] = jreturn pipi = prefix_function(needle)print(pi)i ,j = 0,0        while i < m and j < n:while  j > 0 and haystack[i] != needle[j]:j = pi[j-1]if haystack[i] == needle[j]:               j += 1if j == n:return i - j + 1i += 1return -1

三、其他

四、更多例题

五、参考链接