牛客网 4370B (Trie树)

题目链接：https://ac.nowcoder.com/acm/contest/4370/B

查询字符集中是否有字符串是另一字符串的前缀
Trie 树边插入边判断即可
注意每次把 Trie 树清空

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;

const int maxn = 1001000;

int T,Case = 0;
int N, root = 0, cnt = 0;

char str[maxn];

struct Node{
	int son[10];
	int mark;
}trie[maxn];

bool insert(char *s){
	int pos = root; int flag = 0, pre = cnt;
	for(int i=0;i<strlen(s);++i){
		int num = s[i] - '0';
		if(!trie[pos].son[num]) trie[pos].son[num] = ++cnt;
		pos = trie[pos].son[num];
		if(trie[pos].mark) flag = 1;
	}
	trie[pos].mark = 1;
	
	if(flag || pre == cnt) return false;
	else return true;
}

ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f; }

int main(){
	T = read();
	while(T--){
		for(int i=0;i<=cnt;++i){
			memset(trie[i].son,0,sizeof(trie[i].son));
			trie[i].mark = 0;
		}
		++Case; cnt = 0;
		int flag = 0;
		N = read();
		for(int i=1;i<=N;++i){
			scanf("%s",str);
			if(!insert(str)){
				flag = 1;
			}
		}
		if(!flag){
			printf("Case #%d: Yes
",Case);
		}else{
			printf("Case #%d: No
",Case);
		}
	}
	
	return 0;
}