String Trie

String Trie

Implementation

const int K=26; //size of used alphabets.
const int N=2e5+5;

struct Vertex{
	int nxt[K];
	bool isLeaf=false;
	Vertex(){
		fill(nxt,nxt+K,-1);
	}
};

vector<Vertex> trie(1); // trie
vector<int> path[N]; // save the path of strings on trie
string s[N];

void add(int id,const string& s){
	int v=0;
	for(const char& ch:s){
		int c=ch-'a';
		path[id].pb(v);
		if(trie[v].nxt[c]==-1){
			trie[v].nxt[c]=trie.size();
			trie.emplace_back();
		}
		v=trie[v].nxt[c];
	}
	trie[v].isLeaf=true;
}