LightOJ 1129 - Consistency Checker Trie树模板

题意：给出n条串判断是否存在一个串为另一个串的前缀。
思路：套Trie树的模板，先全部插入，再查找每个字串，如果查找字串完毕，但还存在下一个节点，说明存在前缀。

/** @Date    : 2016-11-09-20.09
  * @Author  : Lweleth ([email protected])
  * @Link    : https://github.com/
  * @Version :
  */
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <utility>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <stack>
#include <queue>
#define LL long long
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1e5+20;

char a[10010][15];
struct yuu
{
    int cnt;
    int p;
    int nxp[N][12];


    int init()
    {
        memset(nxp[0], INF, sizeof(nxp[0]));//  
        cnt = 1;//
        p = 0;
    }

    int idx(char a)
    {
        return a - '0';
    }

    void Insert(char *s)
    {
        int t = p;
        int x = strlen(s);
        for(int i = 0; i < x; i++)
        {
            int c = idx(s[i]);
            if(nxp[t][c] == INF)
            {
                memset(nxp[cnt], INF, sizeof(nxp[cnt]));//注意此处初始化的是下一个下标所在的空间
                nxp[t][c] = cnt;
                //cout << cnt << endl;
                cnt++;
            }
            t = nxp[t][c];//
        }

    }

    int Find(char *s)
    {
        int t = p;
        int x = strlen(s);
        for(int i = 0; i < x; i++)
        {
            int c = idx(s[i]);
            //cout << i << "~" << c <<endl;
            if(nxp[t][c] == INF)
                return 0;
            t = nxp[t][c];
        }
        for(int i = 0; i < 10; i++)
        {
            if(nxp[t][i] != INF)
                return 1;
        }
        return 0;
    }

}tt;




int main()
{
    int T;
    int cnt = 0;
    cin >> T;
    while(T--)
    {
        int n;
        scanf("%d", &n);
        MMF(a);
        tt.init();
        for(int i = 0; i < n; i++)
        {
            scanf("%s", a[i]);
            tt.Insert(a[i]);
        }
        int flag = 0;
        for(int  i = 0; i < n; i++)
        {
            if(tt.Find(a[i]))
            {
                flag = 1;
                break;
            }
        }
        if(!flag)
            printf("Case %d: YES\n", ++cnt);
        else printf("Case %d: NO\n", ++cnt);
    }
    return 0;
}