UVa 12244 Growing Strings

题目描述

Gene\texttt{Gene}Gene和Gina\texttt{Gina}Gina有一个特别的农场，他们种植的是字符串。字符串的生长规则是：只能在左侧和 / 或右侧添加字符，不能丢失字符，也不能在中间插入字符。

他们有若干张照片，每张照片展示一个字符串。由于照片没有标注，他们忘记了每张照片属于哪个字符串。现在需要找出一个最长的照片序列，使得序列中前一张照片的字符串是后一张照片的字符串的连续子串，且所有照片互不相同。

给定若干字符串（照片），求最长合法序列的长度。

输入格式

每个测试用例第一行一个整数NNN（1≤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​是si+1s_{i+1}si+1​的连续子串，并且所有字符串互不相同。

直接暴力枚举所有字符串对，判断子串关系，复杂度为O(N2⋅L)O(N^2 \cdot L)O(N2⋅L)，不可接受（NNN最大10410^4104）。

考虑生长规则：每次只能在两端添加字符。这意味着，如果sis_isi​是si+1s_{i+1}si+1​的子串，那么si+1s_{i+1}si+1​一定可以通过在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标记：标记该节点对应一个模式串的结尾。

算法流程

1. 读入所有字符串，存入数组。
2. 按长度排序：保证处理长字符串时，所有比它短的字符串的dp\textit{dp}dp值已经计算完毕。
3. 将所有字符串插入Aho-Corasick\texttt{Aho-Corasick}Aho-Corasick自动机。
4. 构建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]就表示：以该节点为结尾的字符串，或者它的某个后缀是模式串。
5. 按长度递增顺序处理每个字符串：
   • 在自动机上匹配当前字符串，每匹配一个字符，就沿着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)）。
6. 记录全局最大值作为答案。

正确性说明

• 由于我们按长度从小到大处理，当处理到字符串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//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;namespaceAhoCorasick{constintMAXN=1e6+6;constintALPHA=26;constcharBASE='a';intnxt[MAXN][ALPHA],fail[MAXN],out[MAXN],dp[MAXN];intnodeCnt;voidinitialize(){for(inti=0;i<nodeCnt;++i){memset(nxt[i],0,sizeof(nxt[i]));fail[i]=out[i]=dp[i]=0;}nodeCnt=1;}voidinsert(conststring&s){intu=0;for(charc:s){intidx=c-BASE;if(!nxt[u][idx])nxt[u][idx]=nodeCnt++;u=nxt[u][idx];}out[u]=1;}voidbuild(){queue<int>q;for(inti=0;i<ALPHA;++i){if(nxt[0][i]){fail[nxt[0][i]]=0;q.push(nxt[0][i]);}}while(!q.empty()){intu=q.front();q.pop();out[u]|=out[fail[u]];for(inti=0;i<ALPHA;++i){intv=nxt[u][i];if(v){fail[v]=nxt[fail[u]][i];q.push(v);}else{nxt[u][i]=nxt[fail[u]][i];}}}}intsolve(conststring&s){intu=0,best=1;for(charc:s){u=nxt[u][c-BASE];for(intv=u;v;v=fail[v]){if(out[v])best=max(best,dp[v]+1);}}dp[u]=max(dp[u],best);returnbest;}}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;while(cin>>n,n){vector<string>strs(n);for(inti=0;i<n;++i)cin>>strs[i];sort(strs.begin(),strs.end(),[](conststring&a,conststring&b){returna.size()<b.size();});AhoCorasick::initialize();for(conststring&s:strs)AhoCorasick::insert(s);AhoCorasick::build();intans=0;for(conststring&s:strs)ans=max(ans,AhoCorasick::solve(s));cout<<ans<<'\n';}return0;}