最近情报人员得到了一些经过加密的文章，每个单词都很长。破译人员想到先把单词简化一下，方法是把每个单词尽量取短些的前缀，但所取的前缀不能是其他单词的前缀。
这个任务现在就交给你来完成。
解释：“字符串s1是s2的前缀”是说把字符串s2的后面去掉某些，只保留与s1的长度时，s2就与s1完全相同。如：“abc”是“abcde”和“abc”的前缀，但不是“ababc”的前缀。
第一行一个整数N，表示单词个数。 下面有N行，每行一个单词。
共N行，每行一个单词，是对应上面的N个单词化简后的单词。
3 abc efg ijh
a e I
数据范围 单词数N,1≤N≤50；每个单词的长度不超过50；并且单词都有小写字母构成。 保证所给单词没有一个单词是另一个单词的前缀。
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<iostream> using namespace std; struct pointt { int tto[27],bj,cd;//tto[27]中存的是每一个节点的儿子，bj是标记是否是单词末尾，cd为该节点走过几次 }a[2505]; int num=0; void ins(string s)//建立trie树 { int len=s.size(); int p=0;//最初始的根节点是空节点 for(int i=0;i<len;i++) { int zf=(s[i]-'a'); if(a[p].tto[zf]==0) { a[p].tto[zf]=++num; } p=a[p].tto[zf]; a[p].cd++;//将其下一个点的cd值加1 } a[p].bj=1;//标记单词的结尾 } void matchh(string s)//匹配 { int len=s.size(); int p=0; for(int i=0;i<len;i++) { char q=s[i]; int zf=(s[i]-'a'); p=a[p].tto[zf]; printf("%c",q); if(a[p].cd==1) break; } return; } int main() { int n; scanf("%d",&n); string s[55]; for(int i=1;i<=n;i++) { cin>>s[i]; ins(s[i]); } for(int i=1;i<=n;i++) { matchh((s[i])); printf("\n"); } return 0; }
