@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、判断子序列直接查询。类SubSequenceAuto:def__init__(self,s,abc='abcdefghijklmnopqrstuvwxyz'):self.s,self.abc=s,abcself.n,abc_len=len(s),len(abc)self.abc_index={v:kfork,vinenumerate(abc)}self.dp=[[self.n]*abc_lenfor_inrange(self.n+1)]dp=self.dp#dp.append([self.n]*abc_len)foriinrange(self.n-1,-1,-1):dp[i]=dp[i+1][:]dp[i][self.abc_index[s[i]]]=i#forjinrange(abc_len):#dp[i][j]=iifs[i]==abc[j]elsedp[i+1][j]defquery_is_sub_seq(self,t):dp=self.dpabc_index=self.abc_indexn=self.nr=0forcint:r=dp[r][abc_index[c]]ifr==n:returnFalser+=1returnTrueclass解决方案：defisSubsequence(self,s:str,t:str)->bool:ssa=SubSequenceAuto(t)返回ssa.query_is_sub_seq(s)2。多次询问，使用自动链接：522。长特殊序列II问题的正确解法应该是自动机，但是数据薄弱，每次单次长度<=10，所以可能没有这么简单类SubSequenceAuto:def__init__(self,s,abc='abcdefghijklmnopqrstuvwxyz'):self.s,self.abc=s,abcself.n,abc_len=len(s),len(abc)self.abc_index={v:kfork,vinenumerate(abc)}self.dp=[[self.n]*abc_lenfor_inrange(self.n+1)]dp=self.dp#dp.append([self.n]*abc_len)foriinrange(self.n-1,-1,-1):dp[i]=dp[i+1][:]dp[i][self.abc_index[s[i]]]=i#forjinrange(abc_len):#dp[i][j]=iifs[i]==abc[j]elsedp[i+1][j]defquery_is_sub_seq(self,t):dp=self.dpabc_index=self.abc_indexn=self.nr=0forcint:r=dp[r][abc_index[c]]ifr==n:returnFalser+=1returnTrueclass解决方案：deffindLUSlength(self,strs:List[str])->int:"""先说一个显然：如果s的子序列ss是一个特殊序列，那么s更是特殊序列。因此，本题只需要判断每个字符串是否是其他字符串的子序列即可。判断子序列可以是双指针，也可以使用子序列自动机。"""n=len(strs)flags=[True]*n#每个字符串是否为特殊序列，初始化为0。如果是别人的子序列，则置False#下面判断j是否是i序列的子序列foriinrange(n):sba=SubSequenceAuto(strs[i])forjinrange(n):ifi==jorflags[j]==False:如果sba.query_is_sub_seq(strs[j])继续:flags[j]=Falseans=-1foriinrange(n):ifflags[i]:ans=max(ans,len(strs[i]))returnans3.其他1)待补充4，更多例子待补充5.参考链接我的解决方案：Python子序列自动机实践人生苦短，我用Python！
