撰写Description:
Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let’s say the phone catalogue listed these numbers:
- Emergency 911
- Alice 97 625 999
- Bob 91 12 54 26
In this case, it’s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob’s phone number. So this list would not be consistent.
Input:
The first line of input gives a single integer, 1 ≤ t ≤ 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 ≤ n ≤ 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.
Output:
For each test case, output “YES” if the list is consistent, or “NO” otherwise.
Sample Input:
Sample Output:
题意：输入n个字符串，判断是否有某个字符串为另一字符串的前缀。
题解：用字典树进行动态处理，每次输入一个新的字符串进入字典树时即时判断，假设该串输入会导致前缀出现，我们可以分三种情况：
1.该串将树中某串当作前缀，此时该串的长度大等于前缀串，所以当输入串的字符在树中相同位置出现过时，直接判断该字符是否为结尾即可。
2.该串当作树中某串的前缀，此时该串的长度短，所以判断当输入串的字符在树中相同位置出现并出现于最后一位时，存在前缀串。
代码：
不能过于依赖于错误提示，比如把数组开炸了有时候提示TLE…
另外，要特别注意多组数组的tot，end[],trie[][]的初始化以及各数组的大小。
一般来说，maxn=字符串个数*字符串长度，MAXN=字符串种类，trie[maxn][MAXN]，end[maxn]。
//#include<bits/stdc++.h>
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
return b ? gcd(b, a%b) : a;
}
const int maxn = 1e5+10;
int trie[maxn][10],tot=0;
bool end[maxn];
char s[maxn];
bool insert(char *str) {
int len = strlen(str), p=0;
int cnt=0;
for(int k=0; k<len; k++) {
int ch=str[k]-'0';
if(trie[p][ch]==0) {
trie[p][ch]=++tot;
}else{
if(k==len-1){
return false;
}
if(end[trie[p][ch]])return false;
}
p=trie[p][ch];
}
end[p]=1;
return true;
}
// bool search(char *str) {
// int len=strlen(str),p=0;
// for(int i=0; i<len; i++) {
// int ch=str[i]-'0';
// if(trie[p][ch]==0)return true;
// p=trie[p][ch];
// if(end[p])return false;
// }
// return false;
// }
int main() {
int n,m;
scanf("%d", &m);
while(m--) {
tot=0;
CLR(end);
CLR(trie);
scanf("%d",&n);
int flag=1;
while(n--) {
scanf("%s", s);
if(flag==1)flag=insert(s);
}
if(flag)puts("YES");
else puts("NO");
}
return 0;
}
//搜完不死或者搜到结尾就是前缀
//前缀的条件是end[p]=1;
//不死的条件是搜完走人