#1177128 (C++17) No.3626 Not a Prefix

• 問題: No.3626 Not a Prefix
• ユーザー: GOTKAKO
• 提出日時: 2026-08-15 00:02:44
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 98 ms / 2,000 ms
• コード長: 3,593 bytes
• コンパイル時間: 1,218 ms
• コンパイル使用メモリ: 224,596 KB
• 実行使用メモリ: 149,388 KB
• 最終ジャッジ日時: 2026-08-15 00:02:48
• 合計ジャッジ時間: 4,076 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

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

ソースコード

#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();} 

    string query(int M){
        bool ok = false;
        string ret = "";
        auto dfs = [&](auto dfs,int pos,int left) -> void {
            auto &now = Graph.at(pos);
            for(int i=0; i<C; i++) if(now.To.at(i) != -1){
                int to = now.To.at(i);
                left -= Graph.at(to).times;
            }
            for(int i=0; i<C; i++){
                int to = now.To.at(i);
                if(to == -1 && left <= 0){
                    ret += 'a'+i;
                    ok = true; return;
                }
                else if(to != -1){
                    left += Graph.at(to).times;
                    ret += 'a'+i;
                    if(left <= 0){ok = true; return;}
                    dfs(dfs,to,left);
                    if(ok) return;
                    ret.pop_back();
                    left -= Graph.at(to).times;
                }
            }
        };
        dfs(dfs,0,M);
        if(ok) ret = "Yes\n"+ret;
        else ret = "No";
        return ret;
    }
};

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

    int N,M; cin >> N >> M;
    Trie Z; Z.make(26,'a');
    while(N--){
        string s; cin >> s;
        Z.insert(s);
    }
    cout << Z.query(M) << "\n"; 
}