【POJ 3630】 Phone List

【题目链接】

http://poj.org/problem?id=3630

【算法】

字典树

【代码】

#include <algorithm>

#include <bitset>

#include <cctype>

#include <cerrno>

#include <clocale>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <limits>

#include <list>

#include <map>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <utility>

#include <vector>

#include <cwchar>

#include <cwctype>

#include <stack>

#include <limits.h>

using namespace std;

#define MAXN 10010

int i,TC,n;

bool flag;

char s[MAXN][];

struct info

{

        int child[];

        bool is_last;

};

class Trie

{

        private :

                int tot;

                info a[MAXN*];

        public :

                inline void clear(int x)

                {

                        int i;

                        a[x].is_last = false;

                        for (i = ; i < ; i++)

                        {

                                if (a[x].child[i])

                                {

                                        tot--;

                                        clear(a[x].child[i]);

                                        a[x].child[i] = ;

                                }

                         }

                }

                inline bool insert(char *s)

                {

                        int i,x = ,len;

                        bool flag = false;

                        len = strlen(s);

                        for (i = ; i < len; i++)

                        {

                                if (a[x].child[s[i]-''])

                                {

                                        x = a[x].child[s[i]-''];

                                        if (a[x].is_last || i == len - ) flag = true;

                                } else

                                {

                                        a[x].child[s[i]-''] = ++tot;

                                        x = a[x].child[s[i]-''];

                                }

                        }

                        a[x].is_last = true;

                        return flag ^ ;

                }

} T;

int main()

{

        scanf("%d",&TC);

        while (TC--)

        {

                flag = true;

                T.clear();

                scanf("%d",&n);

                for (i = ; i <= n; i++) scanf("%s",&s[i]);

                for (i = ; i <= n; i++)

                {

                        if (T.insert(s[i])) continue;

                        else

                        {

                                flag = false;

                                break;

                        }

                }

                if (flag) printf("YES\n");

                else printf("NO\n");

        }

        return ;

}