SPOJ PHONELST - Phone List | UVA11362 Phone List | LibreOJ10049. 「一本通 2.3 例 1」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;

}

巴特西

SPOJ PHONELST - Phone List | UVA11362 Phone List | LibreOJ10049. 「一本通 2.3 例 1」Phone List

简要题意

思路

代码

最新文章

热门文章