python刷题模板-子序列自动机

@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！

喜欢 (0)赏

[搞代码]

分享 (0)