#pragma once
#include <bits/stdc++.h>
usingnamespacestd;template<intchar_size,intbase>structTrie{structNode{vector<int>child,accept;intc,common;Node(intc):c(c),common(0){child.assign(char_size,-1);}};vector<Node>tree;introot;Trie():root(0){tree.push_back(Node(root));}voidinsert(conststring&s,intid){intnode_id=0;for(inti=0;i<(int)s.size();++i){intc=(int)(s[i]-base);int&next_id=tree[node_id].child[c];if(next_id<0){next_id=(int)tree.size();tree.push_back(Node(c));}++tree[node_id].common;node_id=next_id;}++tree[node_id].common;tree[node_id].accept.push_back(id);}// insert s to Trievoidinsert(conststring&s){insert(s,tree[0].common);}// return the number of s in Trieintsearch(conststring&s,boolprefix=false){intnode_id=0;for(inti=0;i<(int)s.size();++i){intc=(int)(s[i]-base);int&next_id=tree[node_id].child[c];if(next_id<0)return0;node_id=next_id;}returnprefix?1:(int)tree[node_id].accept.size();}// if prefix of s in Trieboolprefix(conststring&s){returnsearch(s,true)>0;}};// Trie<26,'a'> tr
#line 2 "string/trie.cpp"
#include <bits/stdc++.h>
usingnamespacestd;template<intchar_size,intbase>structTrie{structNode{vector<int>child,accept;intc,common;Node(intc):c(c),common(0){child.assign(char_size,-1);}};vector<Node>tree;introot;Trie():root(0){tree.push_back(Node(root));}voidinsert(conststring&s,intid){intnode_id=0;for(inti=0;i<(int)s.size();++i){intc=(int)(s[i]-base);int&next_id=tree[node_id].child[c];if(next_id<0){next_id=(int)tree.size();tree.push_back(Node(c));}++tree[node_id].common;node_id=next_id;}++tree[node_id].common;tree[node_id].accept.push_back(id);}// insert s to Trievoidinsert(conststring&s){insert(s,tree[0].common);}// return the number of s in Trieintsearch(conststring&s,boolprefix=false){intnode_id=0;for(inti=0;i<(int)s.size();++i){intc=(int)(s[i]-base);int&next_id=tree[node_id].child[c];if(next_id<0)return0;node_id=next_id;}returnprefix?1:(int)tree[node_id].accept.size();}// if prefix of s in Trieboolprefix(conststring&s){returnsearch(s,true)>0;}};// Trie<26,'a'> tr