P9364题解

Nuyoah_awa · 2023-07-11 11:22:14 · 题解

题目大意

给定 n 个字符串，当一个字符串的所有子串均出现过时，我们称这个字符串为「完美单词」。

求这些字符串中长度最长的「完美单词」的长度。

题目分析

首先来想暴力，枚举每一个字符串，判断其是否为「完美单词」，如果是，更新最长长度。

看似上述算法的时间复杂度是 \mathcal O(n \times |s_n|^2) 的，肯定过不了。

但是我们可以发现，对于一个「完美单词」，他最多需要 \dfrac{|s|\times(|s| + 1)}{2} 个互不相同的子串，也就是说，10^5 个互不相同的字符串最多构成长度大约为 450 的字符串，所以一个字符串如果不是「完美单词」最多只需要判断 2 \times 10 ^5 次就可以判断出来了。

但是最多只有 26 个字母，也就是说会有很多重复的子串，所以肯定跑不满 \mathcal O(n \times V)（V 表示判断次数，本题中为 2 \times 10 ^ 5），总的时间复杂度最多也就是 \mathcal O(n \log |s|) 的（省略常数）。

再说一些细节：

• 我们可以从长度较长的字符串开始判断，这样第一个「完美单词」一定是最长的。
• 我们可以写一个 \operatorname{check} 函数，每回发现没出现过的子串时，就说明这个字符串一定不是「完美单词」，后面的子串也就没必要判断了。
• 我们可以把所有的字符串丢进一个 \operatorname{map} 里面，这样就可以实现 \mathcal O(\log n) 判断是否出现过了。
• 我们可以使用 \operatorname{substr} 来枚举子串，加上 \operatorname{map} 判断，总的判断效率仍然是 \mathcal O(\log n) 的。

code

#include <iostream>
#include <cstdio>
#include <map>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 5;
int n;
string s[N];
map <string, bool> mp;

bool cmp(string u, string v)
{
    return u.size() > v.size();
}

bool check(string s)
{
    for(int i = s.size() - 2;i >= 1;i--)
        for(int j = 1;j + i <= s.size();j++)
            if(mp[s.substr(j, i)] == false)
                return false;
    return true;
}

signed main()
{
    scanf("%d", &n);
    for(int i = 1;i <= n;i++)
    {
        cin >> s[i];
        mp[s[i]] = true;
        s[i] = "#" + s[i];
    }
    sort(s + 1, s + n + 1, cmp);
    for(int i = 1;i <= n;i++)
    {
        if(check(s[i]))
        {
            printf("%d", s[i].size() - 1);
            return 0;
        }
    }
    return 0;
}