网站建设改版,德阳机械加工网,wordpress主题论坛,wordpress-3.7[python刷题模板] 前缀函数/next数组/kmp算法 一、 算法数据结构1. 描述2. 复杂度分析3. 常见应用4. 常用优化二、 模板代码1. 裸前缀函数2. 树上kmp3. 裸kmp三、其他四、更多例题五、参考链接一、 算法数据结构
1. 描述
前缀函数和next数组基本上是一个东西#…
[python刷题模板] 前缀函数/next数组/kmp算法 一、 算法数据结构1. 描述2. 复杂度分析3. 常见应用4. 常用优化二、 模板代码1. 裸前缀函数2. 树上kmp3. 裸kmp三、其他四、更多例题五、参考链接一、 算法数据结构
1. 描述
前缀函数和next数组基本上是一个东西但储存的内容不同。
他们是kmp算法的基础。但真的不太好理解以及不好写背不过。
前缀函数π(i)可以在O(n)的时间计算出来数组内每个前缀的前缀函数。参考 oiwiki前缀函数与 KMP 算法kmp还可以结合字典树搞ac自动机待施工。前缀函数π[i]代表的前缀s[:i1]和后缀s[-i:]相同的情况下是前缀长度。 简单来说 pi[i] 就是子串 s[0… i] 最长的相等的真前缀与真后缀的长度。 next数组是指模式串在i位置匹配失败后应该向前跳到哪个位置开始继续匹配。
2. 复杂度分析
预处理O(n)查询O(n)
3. 常见应用
字符串查询。
4. 常用优化
从意义上来说前缀函数值得是前后缀相同的长度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,k0,-1while j n-1:if k -1 or p[j] p[k]:j1k1if 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,j1) or dfs_kmp(tree.right,j1)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三、其他
四、更多例题
五、参考链接
