博客

POJ2001


求一群字符串的最短能代表该串的前缀，trie裸题

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN=1024;
const int C_SIZE=32;
const int MAXNNODE=20050;
int ch[MAXNNODE][C_SIZE];
int siz[MAXNNODE];
bool tail[MAXNNODE];
int tot=1;
int newnode(){return ++tot;}
void insert(char *s){
    int lens=strlen(s),cur=0;

    for(int i=0;i<lens;i++){
        siz[cur]++;
        int v=s[i]-'a';
        if(!ch[cur][v]){ch[cur][v]=newnode();}
        cur=ch[cur][v];
    }
    tail[cur]=1;siz[cur]++;
}
void fnd(char *s){
    int lens=strlen(s),cur=0;
    for(int i=0;i<lens;i++){
        putchar(s[i]);
        cur=ch[cur][s[i]-'a'];
        if(siz[cur]==1) break;
    }
    putchar('\n');
}

char s[MAXN][32];
int cnt=0;
int main(){
    while(~scanf("%s",s[++cnt])){
        insert(s[cnt]);
    }
    for(int i=1;i<=cnt;i++) printf("%s ",s[i]),fnd(s[i]);
    return 0;
}