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

• 問題: No.3626 Not a Prefix
• ユーザー: 👑 potato167
• 提出日時: 2026-08-14 21:54:40
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: WA
• 実行時間: -
• コード長: 6,327 bytes
• コンパイル時間: 1,190 ms
• コンパイル使用メモリ: 220,108 KB
• 実行使用メモリ: 148,876 KB
• 最終ジャッジ日時: 2026-08-14 21:54:48
• 合計ジャッジ時間: 3,712 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
sample	AC * 2
other	AC * 22 WA * 23

ソースコード

#line 1 "e.cpp"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll ILL=2167167167167167167;
const int INF=2100000000;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()
template<class T> using pq_ = priority_queue<T, vector<T>, greater<T>>;
template<class T> int LB(vector<T> &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> int UB(vector<T> &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> bool chmin(T &a,T b){if(b<a){a=b;return 1;}else return 0;}
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}
template<class T> void So(vector<T> &v) {sort(v.begin(),v.end());}
template<class T> void Sore(vector<T> &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});}
bool yneos(bool a,bool upp=false){if(a){cout<<(upp?"YES\n":"Yes\n");}else{cout<<(upp?"NO\n":"No\n");}return a;}
template<class T> void vec_out(vector<T> &p,int ty=0){
    if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'<<p[i]<<'"';}cout<<"}\n";}
    else{if(ty==1){cout<<p.size()<<"\n";}for(int i=0;i<(int)(p.size());i++){if(i) cout<<" ";cout<<p[i];}cout<<"\n";}}
template<class T> T vec_min(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;}
template<class T> T vec_max(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;}
template<class T> T vec_sum(vector<T> &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;}
int pop_count(long long a){int res=0;while(a){res+=(int)(a&1),a>>=1;}return res;}
template<class T> T square(T a){return a * a;}

#line 6 "/Users/Shared/po167_library/string/Trie_Tree.hpp"

namespace po167{
template<const int char_size,int base>
struct Trie_Tree
{
    struct Node{
        std::array<int, char_size> next_node;
        std::vector<int> terminate_node;
        int parent_node;
        int char_number;
        int accepet_count;
        explicit Node(int c_):parent_node(-1),char_number(c_),accepet_count(0){
            for(int i=0;i<char_size;i++) next_node[i]=-1;
        }
    };
    std::vector<Node> nodes;
    std::vector<int> fail;
    Trie_Tree(){
        nodes.push_back(Node(-1));
    }
    std::vector<int> insert(std::string &word,int word_id){
        int node_id=0;
        std::vector<int> ids;
        for (char & i : word){
            node_id=min_insert(i,node_id,word_id);
            ids.push_back(node_id);
        }
        nodes[ids.back()].terminate_node.push_back(word_id);
        return ids;
    }
    int min_insert(char ch,int node_id,int word_id){
        int c=(int)(ch-base);
        int next_id=nodes[node_id].next_node[c];
        if(next_id==-1){
            next_id=(int)nodes.size();
            nodes.push_back(Node(c));
        }
        nodes[next_id].parent_node=node_id;
        nodes[node_id].next_node[c]=next_id;
        // nodes[next_id].accept_node.push_back(word_id);
        nodes[node_id].accepet_count++;
        node_id=next_id;
        return node_id;
    }
    void aho(){
        fail.resize(nodes.size());
        std::vector<int> order = {0};
        order.reserve(nodes.size());
        for (int i = 0; i < (int)(order.size()); i++){
            int id = order[i];
            if (id == 0){
                fail[id] = 0;
            }
            else{
                int f = fail[nodes[id].parent_node];
                int c = nodes[id].char_number;
                while (f != fail[f] && nodes[f].next_node[c] == -1){
                    f = fail[f];
                }
                if (nodes[f].next_node[c] != -1 && nodes[f].next_node[c] != id) fail[id] = nodes[f].next_node[c];
                else fail[id] = 0;
            }
            for (int j = 0; j < char_size; j++){
                if (nodes[id].next_node[j] != -1) order.push_back(nodes[id].next_node[j]);
            }
        }
    }

    // node であって、追加した文字列を部分列として含まないものを返す
    // aho を呼んでいないなら呼びます
    std::vector<bool> taboo(){
        if (fail.size() != nodes.size()){
            aho();
        }
        std::vector<int> order = {0};
        std::vector<bool> taboo(nodes.size(), false);
        for (int i = 0; i < (int)order.size(); i++){
            int a = order[i];
            if (!nodes[a].terminate_node.empty()) taboo[a] = true;
            if (taboo[fail[a]]) taboo[a] = true;
            if (a != 0 && taboo[nodes[a].parent_node]) taboo[a] = true;
            for (int j = 0; j < char_size; j++){
                int c = nodes[a].next_node[j];
                if (c != -1) order.push_back(c);
            }
        }    
        return taboo;
    }
};
}
using po167::Trie_Tree;
#line 26 "e.cpp"

void solve();
// DEAR MYSTERIES / TOMOO
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;
    rep(i, 0, t) solve();
}

void solve(){
    int N, M;
    cin >> N >> M;
    Trie_Tree<26, 'a'> T;
    rep(i, 0, N) {
        string S;
        cin >> S;
        T.insert(S, i);
    }
    int ans = 0;
    int rem = N;
    string X, Y;
    auto f = [&](auto self, int a) -> void {
        if (ans + rem < M) return;
        rep(i, 0, 26) {
            if (!Y.empty()) break;
            int ok = 0, nx = -1;
            if (T.nodes[a].next_node[i] == -1) {
                ok = 1;
            }
            else {
                nx = T.nodes[a].next_node[i];
                // cout << nx << " " << T.nodes[nx].accepet_count << ""  << T.nodes[nx].terminate_node.size() << "\n";
                if (ans + rem - T.nodes[nx].accepet_count - T.nodes[nx].terminate_node.size() >= M) {
                    ok = 1;
                }
            }
            if (ok) {
                Y = X;
                Y += (char)('a' + i);
                break;
            }
            else {
                X += (char)('a' + i);
                int s_ans = ans;
                int s_rem = rem;
                ans += rem - T.nodes[nx].accepet_count - T.nodes[nx].terminate_node.size();
                rem = T.nodes[nx].accepet_count;
                self(self, nx);
                ans = s_ans;
                rem = s_rem;
            }
        }
    };
    f(f, 0);
    if (yneos(!Y.empty())) {
        cout << Y << "\n";
    }
}