SPOJ PHONELST - Phone List | UVA11362 Phone List

简要题意

\(t\) 组数据，每组数据给定 \(n\) 个长度不超过 \(10\) 的数字串，判断是否有两个字符串 \(A\) 和 \(B\),满足 \(A\) 是 \(B\) 的前缀，若有，输出 NO ，若没有，输出 YES。

\(1 \leq t \leq 40,1 \leq n \leq 10000\)

思路

\(O(tn^2)\) 的 Hash 无法通过本题，考虑 Trie。

将 \(n\) 个字符串插入一个 Trie，然后枚举字符串 \(B\)，如果存在字符串 \(A\) 是 \(B\) 的前缀，那么在字典树上遍历到 \(B\)，中间必定经过 \(A\) 的最后一个字符表示的节点。

最终思路：将 \(n\) 个字符串插入一个 Trie，我们考虑维护一个布尔数组 \(E\)，\(E_i\) 表示字典树节点 \(i\) 是否为一个输入的字符串的最后一个字符表示的节点，这个好维护。然后枚举 \(B\)，在字典树中 DFS 到 \(B\)，判断沿途节点是否存在 \(E_i=\operatorname{true}\) 即可。

时间复杂度 \(O(10nt)\)。

代码

#include <cstring>
#include <iostream>
#define int long long
using namespace std;

int tree[100005][15],tot;
bool endd[100005];
string s[100005];

void insert(string x,int id){
	int now=0;
	for(char ch:x){
		if(!tree[now][ch-'0']){
			tree[now][ch-'0']=(++tot);
		}
		now=tree[now][ch-'0'];
	}
	endd[now]=1;
}

void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		string x;
		cin>>x;
		insert(x,i);
		s[i]=x;
	}
	for(int i=1;i<=n;i++){
		int now=0;
		for(char ch:s[i]){
			if(endd[now]){
				cout<<"NO"<<'\n';
				return;
			}
			if(!tree[now][ch-'0']){
				tree[now][ch-'0']=(++tot);
			}
			now=tree[now][ch-'0'];
		}
	}
	cout<<"YES"<<'\n';
}

signed main(){
	int t;
	cin>>t;
	while(t--){
		memset(tree,0,sizeof(tree));
		memset(endd,0,sizeof(endd));
		tot=0;
		solve();
	}
	return 0;
}