K – ZZY 的字典
Time Limit: 1000MS
Description
ZZY 的英语一直很悲催..面对厚厚的单词本相当捉急...并且总是将相似的单词给
弄混...囧...为了让自己区分好每个单词但又减少记忆量...ZZY 决定采取将每个单
词简化到最短长度..简化的单词满足在单词表中能唯一标示这个单词并且其长度
最短..若有单词是另一个单词的子集..那么这个单词简化不了..就或者说其简化就
只能是其本身..具体的从样例中可以看出..
Input
多组数据读到文件结束(最多10 组)
每组第一行为单词个数N(1~1000)
每行一个单词..单词长度不超过20 位..每一位都是小写字母..
Output
每组数据先输出一行-------------Case 组号-------------
然后紧跟每行输出对应单词以及其对应的简化记忆单词..
Sample Input
14
awful
attorney
attraction
mancity
avenue
manunit
ax
attribute
averge
aware
arsenal
await
award
oricon
12
carbohydrate
cart
carburetor
caramel
caribou
carbonic
cartilage
carbon
carriage
carton
car
carbonate
Sample Output
-------------Case 1-------------
awful awf
attorney atto
attraction attra
mancity manc
avenue aven
manunit manu
ax ax
attribute attri
averge aver
aware aware
arsenal ar
await awai
award award
oricon o
-------------Case 2-------------
carbohydrate carboh
cart cart
carburetor carbu
caramel cara
caribou cari
carbonic carboni
cartilage carti
carbon carbon
carriage carr
carton carto
car car
carbonate carbona
Source
Tips@USC: ZZY 2011/10/28
#include<iostream>
using namespace std;struct Node
{int flag;Node *next[30];
}node[20001],*root;int nodenum;void insert( char *str )
{int len=strlen(str);int i;int k;int num;Node *tail=root;for( i=0;i<len;i++ ){num=str[i]-'a';if( tail->next[num]==NULL ){Node *p=&node[nodenum++];p->flag=0;tail->next[num]=p;}tail=tail->next[num];tail->flag++;}
}void getAns( char *str )
{int len=strlen(str);int i,num;Node *tail=root;printf( "%s ",str );for( i=0;i<len;i++ ){num=str[i]-'a';if( tail->next[num]->flag==1 ){printf( "%c",str[i] );break;}printf( "%c",str[i] );tail=tail->next[num];}printf( "\n" );
}int main()
{ int n;char date[1002][30];int T=0;while( scanf( "%d",&n )!=EOF ){int i;memset( node,0,sizeof(node) );root=NULL;nodenum=0;root=&node[nodenum++];for( i=0;i<n;i++ ){scanf( "%s",date[i] );insert( date[i] );}printf( "-------------Case %d-------------\n",++T );for( i=0;i<n;i++ )getAns( date[i] );}return 0;
}