#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define loop(i,a,b) for(int i=a;i pii; typedef vector vi; typedef vector vvi; typedef vector vp; typedef vector vvp; typedef vector vs; typedef vector vd; typedef vector vvd; typedef pair pip; typedef vectorvip; //#define mt make_tuple //typedef tuple tp; //typedef vector vt; templatebool cmin(A &a,const B &b){return a>b?(a=b,true):false;} templatebool cmax(A &a,const B &b){return aconstexpr int size(const C &c){return (int)c.size();} //template constexpr int size(const T (&xs)[N])noexcept{return (int)N;} const double PI=acos(-1); const double EPS=1e-7; Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9; int dx[]={0,1,0,-1}; int dy[]={1,0,-1,0}; #define MAX 26 #define OFFSET 'a' struct Node{ int nxt[MAX+1]; // 次のalphabeteのノード番号 int exist; // 子ども以下に存在する文字列の数の合計 vi accept; // その文字列id Node() : exist(0){memset(nxt, -1, sizeof(nxt));} }; struct Trie{ vectornodes; int root; Trie() : root(0){nodes.push_back(Node());} void update_direct(int node,int id){ nodes[node].accept.push_back(id); } void update_child(int node,int child,int id){ ++nodes[node].exist; } void add(const string &str,int str_index,int node_index,int id){ if(str_index == str.size()) update_direct(node_index, id); else{ const int c = str[str_index] - OFFSET; if(nodes[node_index].nxt[c] == -1) { nodes[node_index].nxt[c] = (int) nodes.size(); nodes.push_back(Node()); } add(str, str_index + 1, nodes[node_index].nxt[c], id); update_child(node_index, nodes[node_index].nxt[c], id); } } void add(const string &str,int id){add(str, 0, 0, id);} void add(const string &str){add(str, nodes[0].exist);} int size(){return (nodes[0].exist);} int nodesize(){return ((int) nodes.size());} }; struct Aho_Corasick : Trie{ static const int FAIL = MAX; vi correct; Aho_Corasick() : Trie() {} void build(){ correct.resize(nodes.size()); rep(i,nodes.size())correct[i]=(int)nodes[i].accept.size(); queue que; rep(i,MAX+1){ if(~nodes[0].nxt[i]) { nodes[nodes[0].nxt[i]].nxt[FAIL] = 0; que.emplace(nodes[0].nxt[i]); }else nodes[0].nxt[i] = 0; } while(!que.empty()) { // rep(i,correct.size())cout<<" "<>s; int n; cin>>n; vs p(n); rep(i,n)cin>>p[i]; Aho_Corasick ac; rep(i,n)ac.add(p[i]); ac.build(); vi out; cout<