poj 3630 Phone List

时间:2021-07-13 03:02:32
 #include<iostream>
#include<cstdio>
#include<cstring>
#define N 100005
using namespace std;
int Trie[N][];
int nodeN;
int main()
{
int t, n, i, j, isPrefix, flag;
char ph[];
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
isPrefix=;
nodeN=;
memset(Trie[], , sizeof(int)*);
for(i=; i<n; ++i)
{
scanf("%s", ph);
flag=;
int cur=;
if(!isPrefix)
for(j=; ph[j]; ++j)
{
int k=ph[j]-'';
if(!Trie[cur][k])
{
if(i!= && !flag)//利用第一个字符串建立一个初始的trie树
{
flag=;//建立了新节点(如果当前 cur 节点还有孩子说明没有公共前缀, 否则说明当前路已经走到了尽头,产生了公共前缀)
int c;
 for(c=; c<; ++c)//检查时候当前节点cur是否有孩子节点
      if(Trie[cur][c])
         break;
      if(c>=)
38       {
       isPrefix=; //没有孩子节点,则说明产生了公共前缀
        break;
     }
    }
Trie[cur][k]=++nodeN;
memset(Trie[nodeN], , sizeof(int)*);
}
cur=Trie[cur][k];
}
if(flag== && i!=)//如果不是第一个字符串,而且在遍历整个树的时候没有发现建立新的节点,则说明当前字符串必然是之前某个字符串的公共前缀
isPrefix=;
}
if(isPrefix)
printf("NO\n");
else printf("YES\n");
}
return ;
}
 /*
好不容易想用一下链表来写一下,还超时啊。。。。
*/
1 #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
class Trie
{
public:
Trie *ch[];
Trie()
{
memset(ch, , sizeof(ch));
}
}; int main()
{
int t, n, i, j, isPrefix, flag;
char ph[];
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
Trie *root=new Trie();
isPrefix=;
for(i=; i<n; ++i)
{
scanf("%s", ph);
flag=;
Trie * cur=root;
if(!isPrefix)
for(j=; ph[j]; ++j)
{
int k=ph[j]-'';
if(!cur->ch[k])
{
if(i!= && !flag)
{
flag=;
int c;
for(c=; c<; ++c)
if(cur->ch[c])
break;
if(c>=)
{
isPrefix=;
break;
}
}
cur->ch[k]=new Trie();
}
cur=cur->ch[k];
}
if(flag== && i!=)
isPrefix=;
}
if(isPrefix)
printf("NO\n");
else printf("YES\n");
}
return ;
}