POJ 2001-Shortest Prefixes(Trie 入门)

题意：给你一组串，求每个串在组中唯一标志的最短前缀

分析：保存树上经过各节点的单词个数，扫描每个串当经过节点单词个数是一（能唯一标志）结束

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <cstdio>

#include <vector>

#include <string>

#include <cctype>

#include <complex>

#include <cassert>

#include <utility>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

typedef long long ll;

#define lson l,m,rt<<1

#define pi acos(-1.0)

#define rson m+1,r,rt<<11

#define All 1,N,1

#define read freopen("in.txt", "r", stdin)

#define N 20010

const ll  INFll = 0x3f3f3f3f3f3f3f3fLL;

const int INF= 0x7ffffff;

const int mod =  ;

struct Trie{

    int ch[N][];

    int val[N],num;

    void init(){

        num=;

        memset(ch[],,sizeof(ch[]));

    }

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

    //建树

    void build(char *s){

        int u=,n=strlen(s);

        for(int i=;i<n;++i){

            int v=idx(s[i]);

            if(!ch[u][v]){

                memset(ch[num],,sizeof(ch[num]));

                ch[u][v]=num++;

            }

            u=ch[u][v];

            val[u]++;

        }

    }

    //查询

    void query(char *s){

        int u=,n=strlen(s);

        for(int i=;i<n;++i){

            int v=idx(s[i]);

            u=ch[u][v];

            printf("%c",s[i]);

            if(val[u]==){

                break;

            }

        }

        printf("\n");

    }

}trie;

int main()

{

    trie.init();

    char a[][];

    int id=;

    while(~scanf("%s",a[id])){

        trie.build(a[id]);

        id++;

    }

    for(int i=;i<id;++i){

        printf("%s ",a[i]);

        trie.query(a[i]);

    }

return ;

}