Trie树小模版

仅供参考

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
struct Trie_Point{
	Trie_Point(){
		memset(ch,0,sizeof(ch));
		sum=0,fa=0,endnum=0;
		isword=false;
	}
	bool isword;
	int ch[10];
	int sum;
	int endnum;
	int fa;
};
inline int read(){
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
vector<Trie_Point>trie;
Trie_Point emp;
int trie_tot=0,emg;
int main(){
	int n=read(),m,build_tot;
	bool ok;
	char c;
	for(register int i=1;i<=n;i++){
		ok=true;
		trie_tot=0;
		vector<Trie_Point>emptyed;
		swap(trie,emptyed);
		trie.push_back(emp);
		m=read();
		build_tot=0;
		c=getchar();
		while(c!='\n'){
			trie.push_back(emp);
			trie_tot++;
			trie[trie_tot].fa=build_tot;
			trie[build_tot].ch[c-48]=trie_tot;
			trie[build_tot].sum++;
			build_tot=trie_tot;
			c=getchar();
		}
		emg=trie_tot;
		trie[emg].endnum++;
		for(register int j=2;j<=m;j++){
			build_tot=0;
			c=getchar();
			while(c!='\n'){
				if(trie[build_tot].ch[c-48]==0){
					trie.push_back(emp);
					trie_tot++;
					trie[trie_tot].fa=build_tot;
					trie[build_tot].ch[c-48]=trie_tot;
					trie[build_tot].sum++;
					build_tot=trie_tot;
				}else build_tot=trie[build_tot].ch[c-48];
				c=getchar();
			}
			trie[build_tot].endnum++;
		}
		if(trie[emg].sum>0||trie[emg].endnum>1)printf("NO\n");
		else printf("YES\n");
	}
	return 0;
}