CUGB专题训练之数据结构：C - Shortest Prefixes 字典树Trie

carbohydrate
cart
carburetor
caramel
caribou
carbonic
cartilage
carbon
carriage
carton
car
carbonate

carbohydrate carboh
cart cart
carburetor carbu
caramel cara
caribou cari
carbonic carboni
cartilage carti
carbon carbon
carriage carr
carton carto
car car
carbonate carbona

trie树的重新练习，与以前做的差不多，都是水题……在建字典树的时候，每个字母的权值都加1 ，如果超过1，说明已经有几个单词重复了。

所以要找出惟一能识别的最短字符串，那就是找到字母为1的时候……

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define f(i,a,n) for(i=a;i<n;i++)
#define F(i,a,n) for(i=a;i<=n;i++)
#define MM 100005
#define M 1005
#define INF 10000007
using namespace std;
string ss[M];
struct Trie
{
    int ch[MM][27],sz;
    int val[MM];
    Trie():sz(1)
    {
        memset(ch,0,sizeof(ch));
        memset(val,0,sizeof(val));
    }
    int idx(char c) {return c-‘a‘;}
    void insert(char *s)
    {
        int u=0,i,c,l=strlen(s);
        for(i=0;i<l;i++)
        {
            c=idx(s[i]);
            if(!ch[u][c]) ch[u][c]=sz++;
            u=ch[u][c];
            val[u]++;
        }
    }
    void query(string s)
    {
        int u=0,i,c,flag=0,l=s.size();
        string sss;
        for(i=0;i<l;i++)
        {
            if(val[u]==1) {cout<<s<<‘ ‘<<sss<<endl;flag=1;break;}
            c=idx(s[i]);
            sss+=s[i];
            u=ch[u][c];
        }
        if(flag==0) cout<<s<<‘ ‘<<sss<<endl;
    }
}T;
int main()
{
    char s[23];
    int i=0;
    while(gets(s))
    {
        T.insert(s);
        ss[i++]=s;
    }
    for(int j=0;j<i;j++)
    {
        T.query(ss[j]);
    }
    return 0;
}

CUGB专题训练之数据结构：C - Shortest Prefixes 字典树Trie,布布扣,bubuko.com

CUGB专题训练之数据结构：C - Shortest Prefixes 字典树Trie

原文：http://blog.csdn.net/u011466175/article/details/20713613