poj 3630 Phone List (带删除操作的静态trie树模板题)

  1/* ***********************************************
  2Author :111qqz
  3Created Time :2016年08月16日 星期二 00时46分23秒
  4File Name :code/poj/3630.cpp
  5************************************************ */
  6#include <cstdio>
  7#include <cstring>
  8#include <iostream>
  9#include <algorithm>
 10#include <vector>
 11#include <queue>
 12#include <stack>
 13#include <set>
 14#include <map>
 15#include <string>
 16#include <cmath>
 17#include <cstdlib>
 18#include <deque>
 19#include <ctime>
 20#define fst first
 21#define sec second
 22#define lson l,m,rt<<1
 23#define rson m+1,r,rt<<1|1
 24#define ms(a,x) memset(a,x,sizeof(a))
 25typedef long long LL;
 26#define pi pair < int ,int >
 27#define MP make_pair
 28using namespace std;
 29const double eps = 1E-8;
 30const int dx4[4]={1,0,0,-1};
 31const int dy4[4]={0,-1,1,0};
 32const int inf = 0x3f3f3f3f;
 33const int N=1E5+7;
 34int n;
 35char s[N][12];
 36int tot;
 37struct Trie
 38{
 39    int nxt[10];
 40    int cnt;
 41
 42    void init()
 43    {
 44	ms(nxt,0);
 45	cnt = 0;
 46    }
 47}trie[N];
 48int add()
 49{
 50    memset(&trie[tot],0,sizeof(Trie));
 51    return tot++;
 52}
 53void Insert(char *s)
 54{
 55    int rt = 0 ;
 56    int len = strlen(s);
 57    for ( int i = 0 ; i < len ; i++)
 58    {
 59	int v = s[i]-'0';
 60	if (!trie[rt].nxt[v]) trie[rt].nxt[v] = add();
 61        rt = trie[rt].nxt[v];
 62	trie[rt].cnt++;
 63    }
 64}
 65void Delete(char *s)
 66{
 67    int rt = 0 ;
 68    int len = strlen(s);
 69    for ( int i = 0 ; i < len ; i++)
 70    {
 71	int v = s[i]-'0';
 72	if (trie[rt].nxt[v])
 73	{
 74	    rt = trie[rt].nxt[v];
 75	    trie[rt].cnt--;
 76	}
 77    }
 78}
 79bool Find(char *s)
 80{
 81    int rt = 0 ;
 82    int len = strlen(s);
 83    for ( int i = 0 ; i < len ;i++)
 84    {
 85	int v = s[i]-'0';
 86	if (!trie[rt].nxt[v]||trie[trie[rt].nxt[v]].cnt==0) return false;
 87	rt = trie[rt].nxt[v];
 88    }
 89    return true;
 90}
 91int main()
 92{
 93	#ifndef  ONLINE_JUDGE 
 94	freopen("code/in.txt","r",stdin);
 95  #endif
 96	int T ; 
 97	cin>>T;
 98	while (T--)
 99	{
100	    scanf("%d",&n);
101	    tot = 1;
102	    trie[0].init();
103	    for ( int i = 1 ; i <= n ; i++)
104	    {
105		scanf("%s",s[i]);
106	//	cout<<"s[i]:"<<s[i]<<endl;
107		Insert(s[i]);
108	    }
109	    bool ok = true;
110	    for ( int i = 1 ; i <= n ; i++)
111	    {
112		Delete(s[i]);
113		if (Find(s[i]))
114		{
115		    ok = false;
116		    break;
117		}
118		Insert(s[i]);
119	    }
120	    if (ok)
121	    {
122		puts("YES");
123	    }
124	    else
125	    {
126		puts("NO");
127	    }
128	}
129  #ifndef ONLINE_JUDGE  
130  fclose(stdin);
131  #endif
132    return 0;
133}