企业官网建设流程全解析

网站联系方式设置要求,慈溪网站制作,网站管理后台密码忘记了,淘宝官网首页图片后缀自动机 资料#xff1a;https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf 一、后缀自动机的定义 后缀自动机#xff08;Suffix Automaton#xff0c;简称 SAM#xff09;是一种压缩存储字符串所有子串…后缀自动机资料https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf一、后缀自动机的定义后缀自动机Suffix Automaton简称 SAM是一种压缩存储字符串所有子串的高效有限状态自动机能够以O(n)的空间和时间复杂度表示字符串的所有后缀及所有子串是处理字符串子串相关问题的核心数据结构。SAM 的核心特征压缩性通过合并等价状态仅用O(n)个状态和转移边表示长度为n的字符串的所有子串总子串数为n(n1)/2直接存储不可行高效性构建时间/空间复杂度均为O(n)支持子串查询、不同子串计数、最长重复子串等问题的线性/对数时间求解。二、后缀自动机的核心概念1. 状态StateSAM 的每个状态代表一组等价的子串称为“等价类”满足这些子串在字符串中出现的结束位置集合endpos完全相同每个状态关联核心属性len该状态表示的子串的最大长度link后缀链接指向另一个状态表示当前状态的子串去掉首字符后的等价状态构成一棵后缀树trans转移字典键为字符值为转移后的状态表示在当前子串末尾添加该字符后的等价状态。2. 结束位置集合endpos对于字符串S的子串tendpos(t)是t在S中所有结束位置的集合。例如S ababa子串aba的endpos {2,4}。等价状态endpos相同的子串属于同一状态状态的len该状态所有子串的最大长度最小长度为link状态的len 1。3. 后缀链接link后缀链接是 SAM 的核心结构满足若状态u的后缀链接指向v则endpos(v) ⊇ endpos(u)所有状态的后缀链接构成一棵以初始状态空串状态为根的树。4. 初始状态与终止状态初始状态起始状态表示空串len 0link -1无父节点终止状态所有能通过后缀链接最终到达初始状态且对应子串为原字符串后缀的状态可通过构建时标记。三、后缀自动机的构建原理SAM 的构建采用增量法逐个添加字符串的字符动态扩展状态和转移核心步骤为“新建状态 → 扩展转移 → 分裂状态若需 → 更新后缀链接”。核心步骤增量法新建状态cur添加字符c时新建状态cur其len last.len 1last为上一个字符对应的状态。扩展转移从last出发沿后缀链接向上遍历为所有无c转移的状态添加指向cur的转移直到初始状态或找到有c转移的状态p。处理转移冲突若p不存在遍历到初始状态则cur.link 初始状态否则找到p通过c转移的状态q若q.len p.len 1直接令cur.link q若q.len p.len 1分裂q为clone状态复制q的trans和linkclone.len p.len 1更新q和cur的link为clone并修正p及其后缀链路上状态的c转移指向clone而非q。更新last令last cur继续添加下一个字符。四、后缀自动机的实现示例classState:def__init__(self):self.len0# 状态表示的子串的最大长度self.link-1# 后缀链接self.transdict()# 转移字典: {字符: 状态索引}classSuffixAutomaton:def__init__(self):self.size1# 状态总数初始状态为0self.last0# 最后一个状态的索引self.states[State()]# 状态列表defsa_extend(self,c):增量添加字符c扩展SAMcurself.size self.size1self.states.append(State())self.states[cur].lenself.states[self.last].len1pself.last# 沿后缀链接向上添加转移whilep!-1andcnotinself.states[p].trans:self.states[p].trans[c]cur pself.states[p].linkifp-1:# 遍历到初始状态cur的后缀链接指向初始状态self.states[cur].link0else:qself.states[p].trans[c]ifself.states[p].len1self.states[q].len:# q是p添加c后的直接状态cur的后缀链接指向qself.states[cur].linkqelse:# 分裂q为clone状态cloneself.size self.size1self.states.append(State())self.states[clone].lenself.states[p].len1self.states[clone].transself.states[q].trans.copy()self.states[clone].linkself.states[q].link# 更新p及其后缀链路上指向q的转移为clonewhilep!-1andself.states[p].trans.get(c,-1)q:self.states[p].trans[c]clone pself.states[p].link# 更新q和cur的后缀链接self.states[q].linkclone self.states[cur].linkclone self.lastcurdefbuild(self,s):构建字符串s的SAMforcins:self.sa_extend(c)defcount_distinct_substrings(self):统计字符串的不同子串数量res0foriinrange(1,self.size):# 每个状态贡献的子串数 len[i] - len[link[i]]resself.states[i].len-self.states[self.states[i].link].lenreturnresdefis_substring(self,t):判断t是否是原字符串的子串p0# 从初始状态开始forcint:ifcnotinself.states[p].trans:returnFalsepself.states[p].trans[c]returnTrue使用示例# 构建SAMsabracadabrasamSuffixAutomaton()sam.build(s)# 统计不同子串数量print(不同子串数量:,sam.count_distinct_substrings())# 输出 53# 子串查询print(是否包含子串 abra:,sam.is_substring(abra))# 输出 Trueprint(是否包含子串 xyz:,sam.is_substring(xyz))# 输出 False# 最长重复子串需额外遍历状态计算deflongest_repeated_substring(sam):max_len0foriinrange(1,sam.size):link_lensam.states[sam.states[i].link].len# 重复子串需满足该状态的子串出现至少两次endpos大小≥2# 简化版通过len - link_len判断可能的最大长度精确判断需统计endposifsam.states[i].lenmax_lenandlink_len0:max_lensam.states[i].lenreturnmax_lenprint(最长重复子串长度:,longest_repeated_substring(sam))# 输出 4如abra五、后缀自动机的核心操作与时间复杂度操作描述时间复杂度构建 SAM增量添加字符动态扩展状态O(n)子串存在性查询沿转移边遍历O(不同子串计数遍历所有状态计算贡献O(n)最长重复子串遍历状态找最大lenO(n)最长公共子串两字符串构建一个字符串的SAM遍历另一个字符串O(nm)六、后缀自动机的典型应用不同子串计数核心公式为∑(len[i] - len[link[i]])所有状态的贡献和子串存在性查询线性时间判断一个字符串是否是原字符串的子串最长重复子串找到最大的len[i]满足该状态的子串出现至少两次最长公共子串对字符串S构建 SAM用字符串T遍历 SAM记录遍历过程中的最大长度子串出现次数统计通过拓扑排序统计每个状态的endpos大小子串出现次数多字符串公共子串构建多个字符串的 SAM合并状态后求解。七、后缀自动机与其他字符串结构的对比数据结构构建复杂度空间复杂度核心优势适用场景后缀自动机较复杂O(n)空间最优支持动态添加海量字符串的子串问题后缀数组中等O(n log n)直观支持LCP问题重复子串、公共子串字典树Trie简单O(n)前缀匹配高效前缀查询、词频统计SAM 的核心优势是空间和时间效率极致尤其适合处理超长字符串如百万级字符的子串问题缺点是理解和实现难度较高而后缀数组更直观适合入门级字符串子串问题。