#include using namespace std; struct Trie{ int C,base,words = 0; struct Node{ int c,times; //今の文字(根は0),この頂点を通った回数->ここまで一致する文字列の数. vector To,accept; //次の文字の行き先,ここで終わる文字列. }; vector Emp; queue reuse; vector 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 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 void { auto &now = Graph.at(pos); for(int i=0; i> N >> M; Trie Z; Z.make(26,'a'); while(N--){ string s; cin >> s; Z.insert(s); } cout << Z.query(M) << "\n"; }