#define _GLIBCXX_DEBUG #include using std::cout; using std::endl; struct trie{ struct node{ std::vector next_alp; int val; node():next_alp(26,-1),val(-1){} node(int k):next_alp(26,-1),val(k){} node(int c,int id):next_alp(26,-1),val(-1){ next_alp[c] = id; } }; std::vector nodes; int k; trie():nodes(26),k(0){} void dump(){ for(int i=0;i encode(std::string const& s){ int n = s.size(); std::vector a(n); for(int i=0;i const& a,int ai,int nodei){ if(ai+1==a.size()){ nodes[nodei].val = k++; return; } auto& nxt = nodes[nodei].next_alp[a[ai+1]]; if(nxt==-1){ nxt = nodes.size(); nodes.emplace_back(); } add_impl(a,ai+1,nxt); } void add(std::string const& s){ add_impl(encode(s),0,s[0]-'a'); } bool find(std::string const& s){ auto cur = nodes[s[0]-'a']; for(int i=0;i+1>s; int m; cin>>m; trie t; for(int i=0;i>c; for(auto& ci:c)ci=tolower(ci); t.add(c); } for(auto& si:s)si=tolower(si); int ans = 0; for(int i=0;i