共计 2232 个字符，预计需要花费 6 分钟才能阅读完成。
@TOC
一、算法 & 数据结构
1. 形容
子序列自动机能够用来解决子序列判断问题：问模式串 p 是否是原串 s 的子序列。当须要对同一个串进行屡次不同模式串匹配时，能够事后对 s 进行自动机的结构。用一次结构开销，节俭询问开销。这类问题奢侈的做法显然是双指针：
- 让 i 在原串 s 上，j 在模式串 p 上。
- 字符相等，模式串能力后移，不同的话，i 要始终后移，直到相等。
- 这个做法复杂度是 O(n+m)，n,m 别离是两个串的长度。
咱们发现：i 后移时，肯定会挪动到后边第一个（最近的），与 p[j] 雷同的字符上。那咱们能够预处理进去原串上每个字符后边的所有字符最近呈现的地位。这就是子序列自动机的做法。- 用 dp 的形式预处理，逆序遍历 s 串，dpi 贮存每个字符后边每个字母最近呈现的地位。
- 这样能够间接转移，省去大量无用扫描。
2. 复杂度剖析
1) 奢侈做法, O(n+m)
2) 自动机：
- 自动机结构复杂度 O(mc)*,c=26 即为字典长度,m 是原串长度。
- 每次匹配复杂度为 O(n)。
3. 常见利用
1) 判断子序列问题，当屡次对同一个原串进行询问时，事后结构原串的自动机。
4. 罕用优化
1) 对 python 来说，从 dp[i+1] 转移到 dp[i] 时，能够间接切片复制，比一个一个赋值快十分多。
二、模板代码
1. 奢侈询问判断子序列
例题: 392. 判断子序列
间接询问。
class SubSequenceAuto:
def __init__(self,s,abc='abcdefghijklmnopqrstuvwxyz'):
self.s,self.abc = s,abc
self.n,abc_len = len(s),len(abc)
self.abc_index = {v:k for k,v in enumerate(abc)}
self.dp = [[self.n]*abc_len for _ in range(self.n+1)]
dp = self.dp
# dp.append([self.n]*abc_len)
for i in range(self.n-1,-1,-1):
dp[i] = dp[i+1][:]
dp[i][self.abc_index[s[i]]] = i
# for j in range(abc_len):
# dp[i][j] = i if s[i]==abc[j] else dp[i+1][j]
def query_is_sub_seq(self,t):
dp = self.dp
abc_index = self.abc_index
n = self.n
r = 0
for c in t:
r = dp[r][abc_index]
if r == n:
return False
r += 1
return True
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
ssa = SubSequenceAuto(t)
return ssa.query_is_sub_seq(s)2. 屡次询问，应用自动机
链接: 522. 最长非凡序列 II
这题正解应该是自动机，然而数据弱，每个单次长度 <=10, 所以可能不如奢侈。
class SubSequenceAuto:
def __init__(self,s,abc='abcdefghijklmnopqrstuvwxyz'):
self.s,self.abc = s,abc
self.n,abc_len = len(s),len(abc)
self.abc_index = {v:k for k,v in enumerate(abc)}
self.dp = [[self.n]*abc_len for _ in range(self.n+1)]
dp = self.dp
# dp.append([self.n]*abc_len)
for i in range(self.n-1,-1,-1):
dp[i] = dp[i+1][:]
dp[i][self.abc_index[s[i]]] = i
# for j in range(abc_len):
# dp[i][j] = i if s[i]==abc[j] else dp[i+1][j]
def query_is_sub_seq(self,t):
dp = self.dp
abc_index = self.abc_index
n = self.n
r = 0
for c in t:
r = dp[r][abc_index]
if r == n:
return False
r += 1
return True
class Solution:
def findLUSlength(self, strs: List[str]) -> int:
"""
先说一个显然：如果 s 的子序列 ss 是一个非凡序列，那么 s 更是非凡序列。因而本题只须要判断每个字符串是否是其它字符串的子序列。判断子序列能够双指针，或者用子序列自动机。"""
n = len(strs)
flags = [True] * n # 每个字符串是否是非凡序列，初始化为 0。如果他是他人的子序列，则置 False
# 以下判断 j 是不是 i 的子序列
for i in range(n):
sba = SubSequenceAuto(strs[i])
for j in range(n):
if i == j or flags[j] ==False:
continue
if sba.query_is_sub_seq(strs[j]):
flags[j] = False
ans = -1
for i in range(n):
if flags[i]:
ans = max(ans,len(strs[i]))
return ans三、其余
1) 待补充
四、更多例题
- 待补充
五、参考链接
-
我的题解: Python 子序列自动机做法
人生苦短，我用 Python！
正文完