本文共 2145 字，大约阅读时间需要 7 分钟。
判断是否有前缀...明显就是一个trie了...裸的不能再裸
注意用动态的trie额外分配内存的时候会TLE...所以就用静态的...
不过静态trie一开始还不太会用...不过后来感觉思路和静态邻接表感觉差不多...
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;//typedef long long LL;//typedef __int64 LL;//typedef long double DB;//typedef unisigned __int64 LL;//typedef unsigned long long ULL;#define EPS 1e-8#define MAXN 100005#define MAXE 300000#define INF 0x3f3f3f3f#define PI acos(-1.0)#define MOD 99991//#define MOD 99990001//#define MOD 1000000007#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define max3(a,b,c) (max(max(a,b),c))#define min3(a,b,c) (min(min(a,b),c))#define mabs(a) ((a<0)?(-a):a)//#define L(t) (t << 1) //Left son t*2//#define R(t) (t << 1 | 1) //Right son t*2+1//#define Mid(a,b) ((a+b)>>1) //Get Mid//#define lowbit(a) (a&-a) //Get Lowbit//int gcd(int a,int b){return b?gcd(b,a%b):a;}//int lcm(int a,int b){return a*b/gcd(a,b);}//std::ios::sync_with_stdio(false);struct trie{ int next[10]; bool vis;}tree[MAXN];struct alpha{ int len ; char ch[11];}str[MAXN];int cnt,n,T,loc;bool judge;void insert(alpha s){ int now = 1,len = s.len; for(int i = 0 ; i < len ; i++) { int tmp = s.ch[i] - '0'; if(tree[now].next[tmp] == -1) { tree[now].next[tmp] = loc; if(i == len-1) tree[loc].vis = true; else tree[loc].vis = false; for(int j = 0 ; j < 10 ; j++) tree[loc].next[j] = -1; now = loc; loc++; }else { now = tree[now].next[tmp]; if(tree[now].vis || (i == len-1)) { judge = true; return; } } }}int main(){// freopen("in.txt","r",stdin);// freopen("out.txt","w",stdout); cin>>T; while(T--) { tree[1].vis = false; judge = false; loc = 2; for(int i = 0 ; i < 10 ; i++) tree[1].next[i] = -1; cin>>n; for(int i = 0 ; i < n ; i++) { scanf("%s",str[i].ch); str[i].len = strlen(str[i].ch); } for(int i = 0 ; i < n ; i++) { if(!judge) insert(str[i]); else break; } if(judge) cout<<"NO"<
转载于:https://www.cnblogs.com/Felix-F/archive/2013/04/23/3223624.html