P9364 [ICPC2022 Xi'an R] Perfect Word

小小小朋友 · 2023-05-30 19:48:08 · 题解

题意

很好理解，找到最长的它的所有非空子串都出现过的字符串。

做法

我们发现这个要求实际上相当苛刻，如果一个字符串满足条件，那么它所有字串都应该满足条件，我们考虑按长度从大到小排序，然后直接枚举每个字符串的子串是否出现过。

字符串总长不超过 10^5，而一个满足要求的字符串的所有子串都会出现，这样看就只有长度小于大约 400 的字符串能成为答案，在最坏情况下约需要判断 100000^{\frac{3}{2}} 次，但是实际上由于字母数量有限，远远跑不满。

我们再利用字符串哈希或者 map/set 存储所有字符串来判断即可通过此题。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
string s[100005];
unordered_map<string,bool> um;
bool cmp(string &a,string &b){
    return a.size()>b.size();
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s[i];
        um[s[i]]=1;
    }
    sort(s,s+n,cmp);//按字符串长度排序
    for(int i=0;i<n;i++){
        bool flag=1;
        for(int p=0;flag&&p<s[i].size();p++){
            for(int k=1;k+p<=s[i].size();k++){
                if(um.find(s[i].substr(p,k))==um.end()){//判断字串是否出现
                    flag=0;break;
                }
            }
        }
        if(flag) {
            cout<<s[i].size();
            return 0;
        }
    }
    return 0;
}