[静态Tire树]poj 3630：Phone List

大致题意：

    给出n个不同长度的数串，如果某个串是另一个串的前缀，输出“NO”，否则输出“YES”。

 

大致思路：

    其实是一个很简单的tire判断，很快就写了出来，但是TLE了。手贱翻了一下discuss才知道，动态tire树每次都new一个对象太费时间，要改用静态数组。遂改之，AC~~

 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include <algorithm>
using namespace std;
const int inf=1<<28;
const int mMax=10005;
const int nMax=50;
class nodea{
public:
    int id;
    bool vis;  //前缀记录标志
    nodea *p[10];
//    nodea(){
//        vis=0;
//        int i;
//        id=-1;
//        for(i=0;i<10;i++)p[i]=NULL;
//    }
};
nodea num[500000];nodea *root;
int x;
nodea * newnodea(){
    nodea * p = num + x++;
    for(int i = 0; i < 10; i++){
        p->p[i] = NULL;
    }
    p->id=-1;
    p->vis=0;
    return p;
}

int cnt;
bool flag;

int getnum(char *s){
    int i;
    nodea *r=root;
    int l=strlen(s);
    for(i=0;i<l;i++){
        r->vis=1;
        if(r->id!=-1)flag=0;
        if(r->p[s[i]-'0']==NULL){
            r->p[s[i]-'0']=newnodea();
        }
        r=r->p[s[i]-'0'];
    }
    if(r->id==-1){
        r->id=cnt;
        cnt++;
        if(r->vis==1){
            flag=0;
        }
        r->vis=1;
    }
    return r->id;
}

int main(){
    int n,i,t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        cnt=1;
        x=0;
        char str[nMax];
        root=newnodea();
        flag=1;
        for(i=0;i<n;i++){
            scanf("%s",str);
            if(flag)getnum(str);
        }
        if(flag){
            printf("YES\n");
        }
        else{
            printf("NO\n");
        }
    }
    return 0;
}