AcWing 161. 电话列表
原题链接
简单
作者:
CCabout
,
2020-11-06 22:00:44
,
所有人可见
,
阅读 592
电话列表(y总代码的搬运工)
#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int son[N][10];
bool f[N];
char str[N];
//判断串是否包含其他串作为前缀,不包含返回true(电话本可用)包含其他串作为前缀(电话本不可用)
bool insert(char* str){
int p=0;
bool is_match=false;//初始值无前缀串
bool has_new_node=false;//初始值没有新节点创建
for(int i=0;str[i];i++){
int u=str[i]-'0';
if(son[p][u]==0){son[p][u]=++idx;has_new_node=true;}//有新节点创建
p=son[p][u];
if(f[p])is_match=true;//存在以p结尾的串
}
f[p]=true;//记录当前串的尾标志
return !is_match && has_new_node;
//str遍历过程未遇到串的结束标记--->即没有串作为他的前缀
//创建了新节点-->即当前串不是其他串的前缀
//同时满足以上两条即可用电话列表
}
int main(){
int t,n;
cin>>t;
while(t--){
cin>>n;
memset(son,0,sizeof son);
memset(f,false,sizeof f);
bool flag=true;
for(int i=0;i<n;i++){
cin>>str;
if(!insert(str))flag=false;//当前输入的串不满足电话列表的条件(有一个不满足flag即为false)
}
if(flag)puts("YES");
else puts("NO");
}
return 0;
}