poj - 3630 - Phone List - c++编程基础

题意：给出n个电话号码（仅由数字0-9组成），问是否存在一个号码是另一个号码的前缀（1 ≤ 测试组数t ≤ 40，1 ≤ n ≤ 10000）。

题目链接：http://poj.org/problem id=3630

——>>做这题太无语啦。。。明明就只是一棵Trip，可直到比赛结束都是TLE，究其原因，太什么啦。。。指针写Trip。。。

此题应用静态数组写Trip。。。

#include   
#include   
#include   
  
using namespace std;  
  
const int maxw = 10 + 5;  
const int maxc = 100000 + 10;  
char p[maxw];  
bool ok, isp[maxc];  
int ch[maxc][10];  
  
struct Trip{  
    int sz;  
  
    Trip(){  
        sz = 1;  
        memset(isp, 0, sizeof(isp));  
        memset(ch, 0, sizeof(ch));  
    }  
  
    int idx(char c){  
        return c - '0';  
    }  
  
    void insert(char *s){  
        int len = strlen(s), i;  
        int u = 0;  
        for(i = 0; i < len; i++){  
            int c = idx(s[i]);  
            if(!ch[u][c]) ch[u][c] = sz++;  
            else{  
                if(i == len-1){  
                    ok = 0;      //目前电话是另外电话的前缀  
                    break;  
                }  
                if(isp[ch[u][c]]){  
                    ok = 0;     //另外电话是目前电话的前缀  
                    break;  
                }  
            }  
            u = ch[u][c];  
        }  
        isp[u] = 1;  
    }  
  
    void solve(){  
        if(ok) puts("YES");  
        else puts("NO");  
    }  
};  
  
int main()  
{  
    int t, n;  
    scanf("%d", &t);  
    while(t--){  
        ok = 1;  
        scanf("%d", &n);  
        Trip trip;  
        for(int i = 0; i < n; i++){  
            scanf("%s", p);  
            if(ok) trip.insert(p);  
        }  
        trip.solve();  
    }  
    return 0;  
}