poj 2001 Shortest Prefixes trie入门

题意:输入不超过1000个字符串，每个字符串为小写字母，长度不超过20；之后输出每个字符串可以简写的最短前缀串；

Sample Input

carbohydrate

cart

carburetor

caramel

caribou

carbonic

cartilage

carbon

carriage

carton

car

carbonate

Sample Output

carbohydrate carboh (carbo不止一个字符串含有，所以不能作为简写符号)

cart cart

carburetor carbu

caramel cara

caribou cari

carbonic carboni

cartilage carti

carbon carbon

carriage carr

carton carto

car car

carbonate carbona

对于trie的理解主要是对空间复杂度的理解；这道题直接使用了26叉trie树，maxnode并不是字符串的个数，而是字符串个数乘以长度，每一个节点还含有26个子节点。其实存储的很稀疏；
在insert中，从根节点开始顺序查找是否有第i个字符的子节点，没有直接重新开一个行向量(++sz)，这就导致了最坏的时间复杂度为maxn * maxl * 26;只是方便查找；查找时直接在线输出即可；

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string.h>

#include<algorithm>

#include<vector>

#include<cmath>

#include<stdlib.h>

#include<time.h>

#include<stack>

#include<set>

#include<map>

#include<queue>

using namespace std;

#define rep0(i,l,r) for(int i = (l);i < (r);i++)

#define rep1(i,l,r) for(int i = (l);i <= (r);i++)

#define rep_0(i,r,l) for(int i = (r);i > (l);i--)

#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)

#define MS0(a) memset(a,0,sizeof(a))

#define MS1(a) memset(a,-1,sizeof(a))

#define MSi(a) memset(a,0x3f,sizeof(a))

#define inf 0x3f3f3f3f

#define lson l, m, rt << 1

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

typedef pair<int,int> PII;

#define A first

#define B second

#define MK make_pair

typedef __int64 ll;

template<typename T>

void read1(T &m)

{

    T x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    m = x*f;

}

template<typename T>

void read2(T &a,T &b){read1(a);read1(b);}

template<typename T>

void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}

template<typename T>

void out(T a)

{

    if(a>) out(a/);

    putchar(a%+'');

}

const int maxl =  *  + ;

struct Trie{

    int ch[maxl][];

    int val[maxl];

    int sz;

    Trie(){sz = ;MS0(ch);MS0(val);}

    void Insert(char *s){

        int u = , n = strlen(s);

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

            int c = s[i] - 'a';

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

                //MS0(ch[u]); //* 开始建trie时，初始化了，这里不能删除加入的信息

                ch[u][c] = sz++;

            }

            u = ch[u][c];

            val[u]++;

        }

    }

    int Find(char *s){

        int u = , n = strlen(s);

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

            int c = s[i] - 'a';

            putchar(s[i]);

            u = ch[u][c];

            if(val[u] == ) break;

        }

    }

}trie;

char s[][];

int main()

{

    int n = ;

    while(scanf("%s",s[n]) == ){

        trie.Insert(s[n++]);

    }

    rep0(i,,n){

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

        trie.Find(s[i]);

        puts("");

    }

    return ;

}

巴特西

poj 2001 Shortest Prefixes trie入门

最新文章

热门文章