Phone List POJ - 3630
题意：
给你n个字符串。要求你判断是否有字符串是其他字符串的 前缀。
思路：
其实就是插入。
这里插入分两种情况。
假如当前的串str为字典里面串的前缀。（这种情况就是插入时，不会碰到新结点）字典里的串是str的前缀。（这种情况插入时，查看当前结点是不是某个串的结尾）
AC
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#define For(i,x,y) for(int i=(x); i<=(y); i++)
#define mst(x,a) memset(x,a,sizeof(x))
using namespace std
;
inline int read(){
int ans
=0;
char r
=getchar();bool neg
=false;
while(r
<'0'||r
>'9'){if(r
=='-')neg
=true;r
=getchar();}
while(r
>='0'&&r
<='9'){ans
=ans
*10+r
-'0';r
=getchar();}
return (neg
)?(-ans
):ans
;
}
void write(int x
){
if(x
<0){putchar('0');x
=-x
;}
if(x
>9)write(x
/10);
putchar(x
%10+'0');
}
const int maxnode
=1e5+10;
const int sigma_size
=10;
int flag
;
struct Trie
{
int ch
[maxnode
][sigma_size
];
bool is_end
[maxnode
];
int sz
;
void clear(){sz
=2;mst(ch
[1],0);mst(is_end
,0);}
int idx(char c
){return c
-'0';}
bool insert(char *s
){
int len
=strlen(s
),u
=1;
bool ok
=true;
for(int i
=0; i
<len
; i
++){
int k
=idx(s
[i
]);
if(!ch
[u
][k
]){
mst(ch
[sz
],0);
ch
[u
][k
]=sz
++;
ok
=false;
}
u
=ch
[u
][k
];
if(is_end
[u
])return true;
}
is_end
[u
]=true;
return ok
;
}
}trie
;
void init(){
trie
.clear();
flag
=true;
}
char s
[maxnode
];
int main()
{
int t
;cin
>>t
;
while(t
--){
int n
;cin
>>n
;
init();
For(i
,1,n
){
scanf("%s", s
);
if(trie
.insert(s
))flag
=false;
}
if(flag
)cout
<<"YES"<<endl
;
else cout
<<"NO"<<endl
;
}
return 0;
}
