P9364 Perfect Word 题解

Demeanor_Roy · 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;   
}