【POJ No. 3630】 电话表 Phone List

【POJ No. 3630】 电话表 Phone List

北大OJ 题目地址

【题意】

给出一个电话号码列表，确定它是否满足一致性（没有号码是另一个号码的前缀）。假设电话目录列出了这些数字：紧急911、爱丽丝97625999、鲍勃91125426，则在这种情况下无法呼叫鲍勃，因为只要拨打了他的电话号码的前三位数字，中心就会将呼叫转接到紧急线路。

所以这个列表不满足一致性。

【输入输出】

输入：

第1行包含一个整数T （1≤T ≤40），表示测试用例的数量。每个测试用例的第1行都是一个整数N （1≤N ≤10000），表示电话号码的数量。接下来的N 行，每行都有唯一的电话号码。

电话号码是最多十位数的序列。

输出：

对每个测试用例，若列表一致，则输出“YES”，否则输出“NO”。

【样例】

【思路分析】

这道题是前缀判断问题，可以用字典树解决。

【算法设计】

① 将每个字符串都依次插入字典树中。

② 在插入过程中判断是否是如下两种情况之一，若是则返回true。

• 若字符串处理完毕仍不为空，则说明该串是其他串的前缀。
• 若遇到单词结束标记，则说明其他串是该串的前缀。

③ 若返回true，则输出“NO”，否则输出“YES”。

【注意】
在插入判断的过程中即使发现不一致，也不可以立即停止。继续读入数据，不插入字典树即可，因为有多个测试用例时，停止读入会造成下一个测试用例数据读入错误。

【算法实现】

#include
#include
#include

using namespace std;
const int maxn=100005;//最多10000个字符串，每个字符串最多10位 
const int maxz=10;//不同字符个数，例如数字10，小写字母26
int trie[maxn][maxz];
bool end[maxn];//标识单词结束 
int n,tot;//字符串数,下标 

bool insert(string s){//将字符串s插入到字典树中 
	int len=s.length(),p=1;
	for(int i=0;i<len;i++){
		int ch=s[i]-'0';//转换成数字
		if(!trie[p][ch]) 
			trie[p][ch]=++tot;//记录下标 
		else if(i==len-1)//字符串处理完毕，仍不空，说明该串是其它串的前缀 
			return true;
		p=trie[p][ch];
		if(end[p])
			return true;
	}
	end[p]=true;//标记单词结束
	return false;
}

int main(){	

	int T;
	bool ans;
	string s;
	cin>>T;
	while(T--){
		memset(trie,0,sizeof(trie));
		memset(end,false,sizeof(end));
		tot=1;
		ans=false;
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>s;
			if(ans)
				continue;
			if(insert(s))//不能立即结束，仍要读取n个串 
				ans=true;
		}
		if(ans)
			cout<<"NO"<<endl;//有前缀输出NO 
		else
			cout<<"YES"<<endl;
	}
	
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55