POJ2001Shortest Prefixes(字典树)

题目大意就是帮你给N条字符串，每条长度不超过20。问要将他们单一识别出来，每个字符串最短可以缩为多短。

如：

abc

abcdefg

adef

这四个字符串就可分别缩写为

abc

abcd

方法：字典树（可以参阅http://s.acmore.net/show_article/show/58）。

另外我还用了一个bool数组last用来记录每个单一识别的字符串最短可以到哪个位置,他的下标就是字典树中每个字母对应的序号

方法如下：（以上面的为例）

当输入的字符串在某一个位置开始与之前的不同，就记录这个不同的字母（设置为true），之后的不再改变

当输入字符串的某位置在建好的树中时，把last加长（设置为true）

第一次输入：abc last[0]=true;

第二次输入：abcdefg last[0]=last[1]=last[2]=last[3]=true;

第三次输入：bc last[0]=true;

第四次输入：adef last[0]=last[1]=true;

这样一来输出端长度就分别为1、4、1、2

代码实现如下：

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <iostream>

 #include <stack>

 #include <set>

 #include <queue>

 #define MAX(a,b) (a) > (b)? (a):(b)

 #define MIN(a,b) (a) < (b)? (a):(b)

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

 #define INF 1000000007

 #define MAXN 20005

 using namespace std;

 int trie[MAXN][],val[MAXN],S;

 bool last[MAXN];

 char ma[][];

 int get_num(char ch){return ch-'a';}

 void init()

 {

     mem(trie);mem(val);

     mem(last);mem(ma);

     S = ;

 }

 void insert(char *s)

 {

     int u=,len = strlen(s);

     int flag = ;

     for(int i=;i<len;i++)

     {

         int c = get_num(s[i]);

         if(!trie[u][c])

         {

             trie[u][c] = S;

             val[u] = ;

             if(flag)//如果与上面的字符串开始不一样，酒吧第一个开始不一样的位置设置为true

             {

                 last[u]=true;

                 flag = ;//之后的依然是false

             }

             u = S;

             S++;

         }

         else if(val[u] == )

         {

             u = trie[u][c];

             last[u] = true;//在查找中发现与已建好的树里面相同的数，那么需要识别的字符串就要相应的加长

         }

     }

     if(val[u]== || val[u] == )return;

     else val[u] = ;

 }

 int main()

 {

     init();

     int T =;

     while(scanf("%s",ma[T])!=EOF)

     {

         insert(ma[T++]);

     }

     for(int i=;i<T;i++)

     {

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

         int u=,j=;

         while(last[u] && ma[i][j])

         {

             printf("%c",ma[i][j]);

             u = trie[u][get_num(ma[i][j++])];

         }

         printf("\n");

     }

     return ;

 }

巴特西

POJ2001Shortest Prefixes(字典树)

最新文章

热门文章