自动搬运

查看原文

来自洛谷，原作者为

	Demeanor_Roy 小时候我们总想去改变别人，后来发现，比起改变，筛选是性价比更高的事。

搬运于2025-08-24 22:47:42，当前版本为作者最后更新于2023-06-02 16:44:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 原题链接。

先将所有字符串存下来按长度从小到大排序。然后依次考虑。

为什么要这样做？考虑对于一个字符串 $s[1 \dots n]$，它是完美单词当且仅当给定的字符串中存在 $s[1 \dots n-1]$ 与 $s[2 \dots n]$ 且它们都是完美的。（当然，长度为 $1$ 时例外。）于是我们长度从小到大考虑就能递推地得出答案。

剩下的问题是如何确认并快速找到那两个字符串。这里我用的是字典树，实际上实现精细可以做到线性。不过没必要，毕竟排序就带了个 $\log$。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=1e5+10;
int n,id,ans,tr[N][30],End[N*30];
string t[N];
bool ex[N];
inline void insert(int cur)
{
	int p=0;
	for(int i=0;i<(int)t[cur].size();i++)
	{
		int to=t[cur][i]-'a';
		if(!tr[p][to]) tr[p][to]=++id;
		p=tr[p][to];
	}
	End[p]=cur;
}
inline bool check(int x)
{
	if((int)t[x].size()==1) return true;
	int p=0;
	for(int i=0;i<(int)t[x].size()-1;i++) p=tr[p][t[x][i]-'a'];
	if(!ex[End[p]]) return false;
	p=0;
	for(int i=1;i<(int)t[x].size();i++)	p=tr[p][t[x][i]-'a'];
	if(!ex[End[p]]) return false;
	return true;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) cin>>t[i];
	sort(t+1,t+n+1,[](string a,string b){return (int)a.size()<(int)b.size();});
	for(int i=1;i<=n;i++) insert(i);
	for(int i=1;i<=n;i++) if(check(i)) ex[i]=true,ans=max(ans,(int)t[i].size());
	printf("%d",ans);
	return 0;	
}