#1187905 (C++17) No.3667 Prefix Count Queries

• 問題: No.3667 Prefix Count Queries
• ユーザー: GOTKAKO
• 提出日時: 2026-09-19 06:26:05
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 35 ms / 2,000 ms
• コード長: 3,196 bytes
• コンパイル時間: 1,527 ms
• コンパイル使用メモリ: 224,116 KB
• 実行使用メモリ: 37,156 KB
• 最終ジャッジ日時: 2026-09-19 06:26:12
• 合計ジャッジ時間: 5,120 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 5
other	AC * 35

ソースコード

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

struct Trie{
    int C,base,words = 0;
    struct Node{
        int c,times; //今の文字(根は0),この頂点を通った回数->ここまで一致する文字列の数.
        vector<int> To,accept; //次の文字の行き先,ここで終わる文字列.
    };
 
    vector<int> Emp;
    queue<int> reuse;
    vector<Node> Graph; //頂点0は根.
    void make(int c,int b){ //文字種数と一番小さい文字.
        C = c,base = b;
        Emp.resize(C,-1);
        Graph.push_back(Node{0,0,Emp,{}});
    }
 
    void insert(string &s,int id){
        int pos = 0; words++;
        for(int i=0; i<s.size(); i++){
            int c = s.at(i)-base;
            int &to = Graph.at(pos).To[c];
            if(to == -1){
                to = Graph.size();
                Graph.push_back({c,0,Emp,{}});
            }
            Graph.at(pos).times++;
            pos = to;
        }
        Graph.at(pos).times++;
        Graph.at(pos).accept.push_back(id);
    };
    void insert(string &s){ //文字列挿入.
        int id = Graph.at(0).times;
        if(reuse.size()) id = reuse.front(),reuse.pop();
        insert(s,id);
    }
    void insertset(string &s){ //既にあれば挿入しない.
        if(findsame(s)) return;
        insert(s);
    }
 
    void erase(string &s){ //文字列削除1個だけ.
        if(!findsame(s)) return;
        int pos = 0; words--;
        for(int i=0; i<s.size(); i++){
            int c = s.at(i)-base;
            int &to = Graph.at(pos).To[c];
            Graph.at(pos).times--;
            pos = to;
        }
        Graph.at(pos).times--;
        assert(Graph.at(pos).accept.size() > 0);
        reuse.push(Graph.at(pos).accept.back()); //lastの最後のidを再利用.
        Graph.at(pos).accept.pop_back();
    }

    int find(string &s,bool prefix){
        int pos = 0;
        for(int i=0; i<s.size(); i++){
            int c = s.at(i)-base;
            int to = Graph.at(pos).To[c];
            if(to == -1) return 0;
            pos = to;
        }
        if(prefix) return Graph.at(pos).times;
        return Graph.at(pos).accept.size();
    }
 
    int findsame(string &s){return find(s,false);}
    int findpref(string &s){return find(s,true);}
    int count(){return words;}
    int size(){return Graph.size();} 

    void query(vector<char> Q){
        stack<int> st; st.push(0);
        for(auto c : Q){
            if(c == '2') st.pop();
            else if(c == '3'){
                int pos = st.top();
                if(pos == -1) cout << "0\n";
                else cout << Graph.at(pos).times << "\n";
            }
            else{
                int v = c-'a',pos = st.top();
                if(pos == -1 || Graph.at(pos).To[v] == -1) st.push(-1);
                else st.push(Graph.at(pos).To[v]);
            }
        }   
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N; cin >> N;
    Trie Z; Z.make(26,'a');
    while(N--){
        string s; cin >> s;
        Z.insert(s);
    }
    cin >> N;
    vector<char> Q(N);
    for(auto &c : Q){
        cin >> c;
        if(c == '1') cin >> c;
    }
    Z.query(Q);
}