poj - 3630 - Phone List

題意：給出n個電話號碼（僅由數字0-9組成），問是否存在一個號碼是另一個號碼的前綴（1 ≤ 測試組數t ≤ 40，1 ≤ n ≤ 10000）。   題目鏈接：http://poj.org/problem?id=3630   ——>>做這題太無語啦。。。明明就只是一棵Trip，可直到比賽結束都是TLE，究其原因，太什麼啦。。。指針寫Trip。。。   此題應用靜態數組寫Trip。。。  

#include <cstdio>  
#include <cstring>  
#include <queue>  
  
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;  
}