#1181838 (C++23(gcc16)) No.3667 Prefix Count Queries

• 問題: No.3667 Prefix Count Queries
• ユーザー: 笹
• 提出日時: 2026-08-31 23:11:40
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0)
• 結果: TLE
• 実行時間: -
• コード長: 3,925 bytes
• コンパイル時間: 5,087 ms
• コンパイル使用メモリ: 358,940 KB
• 実行使用メモリ: 36,524 KB
• 最終ジャッジ日時: 2026-08-31 23:12:20
• 合計ジャッジ時間: 13,806 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 5
other	AC * 31 TLE * 1 -- * 2

ソースコード

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

template<int char_size, int base>
struct Trie {
    struct Node {
        vector<int> next;
        vector<int> accept;
        int c;
        int common;
        Node(int c_) : c(c_), common(0){
            next.assign(char_size, -1);
        }
    };
    vector<Node> nodes;
    int root;
    Trie() : root(0) {
        nodes.push_back(Node(root));
    }

    void insert(const string &word, int word_id) {
        int node_id = 0;
        for (int i = 0;i < word.size();i++) {
            int c = (int)(word[i] - base);
            int next_id = nodes[node_id].next[c];
            if (next_id == -1) {
                next_id = (int)nodes.size();
                nodes[node_id].next[c] = next_id;
                nodes.push_back(Node(c));
            }
            ++nodes[node_id].common;
            node_id = next_id;
        }
        ++nodes[node_id].common;
        nodes[node_id].accept.push_back(word_id);
    }
    void insert(const string &word) {
        insert(word, nodes[0].common);
    }
    bool search(const string &word, bool prefix = false) {
        int node_id = 0;
        for (int i = 0; i < (int)word.size(); i++) {
            int c = (int)(word[i] - base);
            int &next_id = nodes[node_id].next[c];
            if (next_id == -1) {  // 次の頂点が存在しなければ終了
                return false;
            }
            node_id = next_id;
        }
        return (prefix) ? true : nodes[node_id].accept.size() > 0;  // 最後の頂点が受理状態か確認
    }
    // prefix を持つ単語が存在するかの検索
    bool start_with(const string &prefix) {
        return search(prefix, true);
    }
    // 単語数
    int count() const {
        return (nodes[0].common);
    }
    // Trie木のノード数
    int size() const {
        return ((int)nodes.size());
    }
    // 最長共通接頭辞
    string lcp() {
        string ans;
        int node_id = root;

        while (true) {
            int next_id = -1;

            for (int c = 0; c < char_size; c++) {
                if (nodes[node_id].next[c] != -1) {
                    int v = nodes[node_id].next[c];

                    if (nodes[v].common == count()) {
                        next_id = v;
                        break;
                    }
                }
            }

            if (next_id == -1) break;

            ans += char(base + nodes[next_id].c);
            node_id = next_id;
        }

        return ans;
    }
    string lcp(const string &s) {
        int node_id = root;
        string ans;

        for (char ch : s) {
            int c = ch - base;
            int next_id = nodes[node_id].next[c];

            if (next_id == -1) break;

            if (nodes[next_id].common - 1 == 0) break;
            ans += ch;
            node_id = next_id;
        }

        return ans;
    }
};

int main() {
    int n;
    cin >> n;
    Trie<26, 'a'> tr;
    for (int i = 0;i < n;i++) {
        string s;
        cin >> s;
        tr.insert(s);
    }
    string s = "";
    int q;
    cin >> q;
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            char c;
            cin >> c;
            s += c;
        } else if (t == 2) {
            s.pop_back();
        } else {
            if (s == "") {
                cout << n << endl;
                continue;
            }
            int node_id = 0;
            for (int i = 0;i < s.size();i++) {
                int c = (int)(s[i] - 'a');
                int next_id = tr.nodes[node_id].next[c];
                node_id = next_id;
                if (node_id == -1) {
                    break;
                }
            }
            if (node_id == -1) {
                cout << 0 << endl;
            } else {
                cout << tr.nodes[node_id].common << endl;
            }
        }
    }
}