题解归档 - cf104077G

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf104077G
• 本地来源：problems/cf104077G/idea.md
• 题目链接：https://codeforces.com/gym/104077/problem/G
• 原始标题：G - Perfect Word

思路

G - Perfect Word

A non-empty string is perfect if every non-empty substring is present as one of the given strings.

For a string s with length L > 1, every proper substring of s is a substring of either:

• s[0..L-2], or
• s[1..L-1].

Therefore s is perfect iff both its length-L-1 prefix and suffix are perfect. Length-1
strings are perfect by themselves.

Sort unique input strings by length and run this recurrence with a hash set of already-perfect
strings.

代码

来源：problems/cf104077G/solution.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<string> s(n);
    for (auto &x : s) cin >> x;
    sort(s.begin(), s.end(), [](const string &a, const string &b) {
        if (a.size() != b.size()) return a.size() < b.size();
        return a < b;
    });
    s.erase(unique(s.begin(), s.end()), s.end());

    unordered_set<string> good;
    good.reserve(s.size() * 2 + 10);
    int ans = 0;
    for (const string &x : s) {
        bool ok = false;
        int len = (int)x.size();
        if (len == 1) ok = true;
        else {
            string pre = x.substr(0, len - 1);
            string suf = x.substr(1);
            ok = good.count(pre) && good.count(suf);
        }
        if (ok) {
            good.insert(x);
            ans = max(ans, len);
        }
    }
    cout << ans << '\n';
    return 0;
}