#1174064 (C++23(gcc16)) No.3626 Not a Prefix

• 問題: No.3626 Not a Prefix
• ユーザー: 👑 loop0919
• 提出日時: 2026-07-28 22:40:12
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 20 ms / 2,000 ms
• コード長: 4,172 bytes
• コンパイル時間: 1,225 ms
• コンパイル使用メモリ: 185,572 KB
• 実行使用メモリ: 66,076 KB
• 最終ジャッジ日時: 2026-08-14 20:52:29
• 合計ジャッジ時間: 4,554 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 2
other	AC * 45

ソースコード

#include <array>
#include <climits>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Node {
    array<int, 26> child;
    int pass = 0;
    int term = 0;
    Node() { child.fill(-1); }
};

struct TrieResult {
    vector<Node> trie;
    int n;
};

TrieResult read_and_build(istream& in) {
    int n, m;
    in >> n >> m;
    vector<Node> trie;
    trie.reserve(500001);
    trie.emplace_back();
    string s;
    for (int i = 0; i < n; ++i) {
        in >> s;
        int v = 0;
        ++trie[v].pass;
        for (char ch : s) {
            int c = ch - 'a';
            int to = trie[v].child[c];
            if (to == -1) {
                to = static_cast<int>(trie.size());
                trie[v].child[c] = to;
                trie.emplace_back();
            }
            v = to;
            ++trie[v].pass;
        }
        ++trie[v].term;
    }
    return {move(trie), n};
}

int minimum_comparable(const vector<Node>& trie) {
    struct Frame { int v, q; };
    vector<Frame> st;
    st.push_back({0, 0});
    int best = INT_MAX;
    while (!st.empty()) {
        auto [v, q] = st.back();
        st.pop_back();
        if (v != 0) best = min(best, q + trie[v].pass);
        int q_child = q + trie[v].term;
        for (int c = 0; c < 26; ++c) {
            int to = trie[v].child[c];
            if (to == -1) {
                // The root's missing child is also a valid nonempty X.
                best = min(best, q_child);
            } else {
                st.push_back({to, q_child});
            }
        }
    }
    return best;
}

pair<bool, string> solve_trie(const vector<Node>& trie, int comparable_limit) {
    struct Frame {
        int v;
        int q;          // number of input strings equal to proper prefixes of this node
        int next_child; // -1 before checking this node, otherwise next character to inspect
    };

    vector<Frame> st;
    st.reserve(trie.size());
    st.push_back({0, 0, -1});
    string path;
    path.reserve(trie.size());

    while (!st.empty()) {
        Frame& f = st.back();
        if (f.next_child == -1) {
            if (f.v != 0 && f.q + trie[f.v].pass <= comparable_limit) {
                return {true, path};
            }
            f.next_child = 0;
        }

        const int child_q = f.q + trie[f.v].term;
        bool descended = false;
        while (f.next_child < 26) {
            const int c = f.next_child++;
            const int to = trie[f.v].child[c];
            if (to == -1) {
                if (child_q <= comparable_limit) {
                    string answer = path;
                    answer.push_back(static_cast<char>('a' + c));
                    return {true, move(answer)};
                }
            } else {
                path.push_back(static_cast<char>('a' + c));
                st.push_back({to, child_q, -1});
                descended = true;
                break;
            }
        }
        if (descended) continue;

        st.pop_back();
        if (!st.empty()) path.pop_back();
    }
    return {false, {}};
}

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    bool print_min = false;
    if (argc >= 2 && string(argv[1]) == "--minimum-comparable") {
        print_min = true;
    }

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<Node> trie;
    trie.reserve(500001);
    trie.emplace_back();
    string s;
    for (int i = 0; i < n; ++i) {
        cin >> s;
        int v = 0;
        ++trie[v].pass;
        for (char ch : s) {
            int c = ch - 'a';
            int& to = trie[v].child[c];
            if (to == -1) {
                to = static_cast<int>(trie.size());
                trie.emplace_back();
            }
            v = to;
            ++trie[v].pass;
        }
        ++trie[v].term;
    }

    if (print_min) {
        cout << minimum_comparable(trie) << '\n';
        return 0;
    }

    const int comparable_limit = n - m;
    auto [ok, answer] = solve_trie(trie, comparable_limit);
    if (!ok) {
        cout << "No\n";
    } else {
        cout << "Yes\n" << answer << '\n';
    }
}