Trie模板(Phone List)

描述

给定 n 个长度不超过 10 的数字串，问其中是否存在两个数字串 S,T，使得 S 是 T 的前缀，多组数据。

输入

第一行一个整数 T，表示数据组数。

对于每组数据，第一行一个数 n，接下来 n 行输入 n 个数字串。

输出

对于每组数据，若存在两个数字串 S，T，使得 S 是 T 的前缀，则输出 NO ，否则输出 YES 。

请注意此处结果与输出的对应关系！

输入样例1

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

输出样例 1

NO
YES

Code:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
typedef long long ll;
typedef unsigned long long ull;

using namespace std;

int son[100005][15], ind = 0;
bool mk[100005];
bool add(char x[])
{
	int l = strlen(x), p = 0;
	bool flag = 0;
	for(int i = 0; i < l; i++)	
	{
		int c = x[i] - '0';
		if(!son[p][c])
		{
			son[p][c] = ++ind;
		}
		p = son[p][c];
		if(mk[p])
		{
			flag = 1;
		}
	}
	mk[p] = 1;
	return flag;
}
int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		ind = 0;
		int n;
		char in[15];
		scanf("%d", &n);
		bool flag = 0;
		for(int i = 1; i <= n; i++)
		{
			scanf("%s", in);
			if(add(in))
			{
				flag = 1;
			}
		}
		if(flag)
		{
			printf("NO\n");
		}
		else
		{
			printf("YES\n");
		}
		memset(son, 0, sizeof(son));
		memset(mk, 0, sizeof(mk));
	}
	return 0;
}