UVa 12244 Growing Strings

题目描述Gene\texttt{Gene}Gene和Gina\texttt{Gina}Gina有一个特别的农场他们种植的是字符串。字符串的生长规则是只能在左侧和 / 或右侧添加字符不能丢失字符也不能在中间插入字符。他们有若干张照片每张照片展示一个字符串。由于照片没有标注他们忘记了每张照片属于哪个字符串。现在需要找出一个最长的照片序列使得序列中前一张照片的字符串是后一张照片的字符串的连续子串且所有照片互不相同。给定若干字符串照片求最长合法序列的长度。输入格式每个测试用例第一行一个整数NNN1≤N≤1041 \le N \le 10^41≤N≤104接下来NNN行每行一个不同的非空字符串由小写字母组成长度不超过100010001000。所有字符串的总长度不超过10610^6106。输入以一行000结束。输出格式对于每个测试用例输出一行一个整数表示最长序列的长度。样例输入6 plant ant cant decant deca an 2 supercalifragilisticexpialidocious rag 0输出4 2题目分析本题的核心是在给定的字符串集合中找到最长的链s1,s2,…,sks_1, s_2, \dots, s_ks1​,s2​,…,sk​使得sis_isi​是si1s_{i1}si1​的连续子串并且所有字符串互不相同。直接暴力枚举所有字符串对判断子串关系复杂度为O(N2⋅L)O(N^2 \cdot L)O(N2⋅L)不可接受NNN最大10410^4104。考虑生长规则每次只能在两端添加字符。这意味着如果sis_isi​是si1s_{i1}si1​的子串那么si1s_{i1}si1​一定可以通过在sis_isi​的左右两侧添加若干字符得到。因此子串关系具有传递性。我们可以将所有字符串按长度从小到大排序。设dp[s]\textit{dp}[s]dp[s]表示以字符串sss结尾的最长链的长度则有dp[s]max⁡{dp[t]1∣t 是 s 的子串且 t≠s} \textit{dp}[s] \max \{ \textit{dp}[t] 1 \mid t \text{ 是 } s \text{ 的子串且 } t \neq s \}dp[s]max{dp[t]1∣t是s的子串且ts}初始条件dp[s]1\textit{dp}[s] 1dp[s]1单个字符串自己形成长度为111的链。问题的关键转化为对于当前字符串sss如何快速找到所有属于集合且是sss的子串的ttt。解题思路子串匹配的优化枚举sss的所有子串并判断是否在集合中时间复杂度为O(L2)O(L^2)O(L2)LLL为字符串长度总复杂度O(∑L2)O(\sum L^2)O(∑L2)在LLL较大时可能超时。我们需要一个能够快速匹配多个模式串的数据结构 ——Aho-Corasick\texttt{Aho-Corasick}Aho-Corasick自动机。Aho-Corasick\texttt{Aho-Corasick}Aho-Corasick自动机简介Aho-Corasick\texttt{Aho-Corasick}Aho-Corasick自动机是一种多模式匹配算法可以在O(文本长度模式串总长)O(\text{文本长度} \text{模式串总长})O(文本长度模式串总长)的时间内找出文本串中所有出现的模式串。其核心结构包括Trie\texttt{Trie}Trie树存储所有模式串。fail\textit{fail}fail指针类似KMP\texttt{KMP}KMP的next\textit{next}next数组用于在匹配失败时跳转到最长后缀节点。output\textit{output}output标记标记该节点对应一个模式串的结尾。算法流程读入所有字符串存入数组。按长度排序保证处理长字符串时所有比它短的字符串的dp\textit{dp}dp值已经计算完毕。将所有字符串插入Aho-Corasick\texttt{Aho-Corasick}Aho-Corasick自动机。构建fail\textit{fail}fail指针同时将fail\textit{fail}fail链上的output\textit{output}output信息通过按位或传递到当前节点即out[u]∣out[fail[u]]\textit{out}[u] \mid \textit{out}[\textit{fail}[u]]out[u]∣out[fail[u]]。这样每个节点的out[u]\textit{out}[u]out[u]就表示以该节点为结尾的字符串或者它的某个后缀是模式串。按长度递增顺序处理每个字符串在自动机上匹配当前字符串每匹配一个字符就沿着fail\textit{fail}fail链向上检查所有有out\textit{out}out标记的节点更新当前字符串的dp\textit{dp}dp值。匹配结束后将当前字符串的dp\textit{dp}dp值存储到其对应的终止节点上即dp[u]max⁡(dp[u],best)\textit{dp}[u] \max(\textit{dp}[u], \textit{best})dp[u]max(dp[u],best)。记录全局最大值作为答案。正确性说明由于我们按长度从小到大处理当处理到字符串sss时所有长度小于∣s∣|s|∣s∣的字符串的dp\textit{dp}dp值已经计算完毕。在自动机上匹配sss的过程中每到达一个节点uuu沿着fail\textit{fail}fail链向上即可访问到所有以当前位置结尾的模式串这些模式串都是sss的子串。因此dp[s]\textit{dp}[s]dp[s]能够正确地从其所有子串的dp\textit{dp}dp值转移而来。复杂度分析构建Trie\texttt{Trie}Trie树O(∑∣si∣⋅Σ)O(\sum |s_i| \cdot \Sigma)O(∑∣si​∣⋅Σ)其中Σ26\Sigma 26Σ26。构建fail\textit{fail}fail指针O(∑∣si∣⋅Σ)O(\sum |s_i| \cdot \Sigma)O(∑∣si​∣⋅Σ)。匹配过程每个字符串的每个字符沿着fail\textit{fail}fail链向上跳的次数在均摊意义下为O(1)O(1)O(1)因为每个字符的fail\textit{fail}fail跳转次数与树高有关但通过out\textit{out}out传递优化后实际总复杂度为O(∑∣si∣)O(\sum |s_i|)O(∑∣si​∣)。总时间复杂度O(∑∣si∣⋅Σ)O(\sum |s_i| \cdot \Sigma)O(∑∣si​∣⋅Σ)空间复杂度O(∑∣si∣⋅Σ)O(\sum |s_i| \cdot \Sigma)O(∑∣si​∣⋅Σ)。代码实现// Growing Strings// UVa ID: 12244// Verdict: Accepted// Submission Date: 2026-06-03// UVa Run Time: 1.680s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;namespaceAhoCorasick{constintMAXN1e66;constintALPHA26;constcharBASEa;intnxt[MAXN][ALPHA],fail[MAXN],out[MAXN],dp[MAXN];intnodeCnt;voidinitialize(){for(inti0;inodeCnt;i){memset(nxt[i],0,sizeof(nxt[i]));fail[i]out[i]dp[i]0;}nodeCnt1;}voidinsert(conststrings){intu0;for(charc:s){intidxc-BASE;if(!nxt[u][idx])nxt[u][idx]nodeCnt;unxt[u][idx];}out[u]1;}voidbuild(){queueintq;for(inti0;iALPHA;i){if(nxt[0][i]){fail[nxt[0][i]]0;q.push(nxt[0][i]);}}while(!q.empty()){intuq.front();q.pop();out[u]|out[fail[u]];for(inti0;iALPHA;i){intvnxt[u][i];if(v){fail[v]nxt[fail[u]][i];q.push(v);}else{nxt[u][i]nxt[fail[u]][i];}}}}intsolve(conststrings){intu0,best1;for(charc:s){unxt[u][c-BASE];for(intvu;v;vfail[v]){if(out[v])bestmax(best,dp[v]1);}}dp[u]max(dp[u],best);returnbest;}}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;while(cinn,n){vectorstringstrs(n);for(inti0;in;i)cinstrs[i];sort(strs.begin(),strs.end(),[](conststringa,conststringb){returna.size()b.size();});AhoCorasick::initialize();for(conststrings:strs)AhoCorasick::insert(s);AhoCorasick::build();intans0;for(conststrings:strs)ansmax(ans,AhoCorasick::solve(s));coutans\n;}return0;}