一个字符串的前缀是从该字符串的第一个字符起始的一个子串。例如“carbon”的前缀是有“c”，“ca”，“car”，“carb”，“carbo”，和“carbon”。空串不是前缀，但是每个非空串是它自身的子串。 我们希望能用前缀来缩略地表示单词。例如“carbohydrate”通常用“carb”来表示。在下面的例子中，“carbohydrate”能被缩写成“carboh”，但是不能被缩写成“carbo”（或其余更短的前缀），因为已经有一个单词用“carbo”开始。 carbohydrate cart carbonic caribou carriage car 一个完全匹配会覆盖一个前缀匹配，例如“car”完全匹配单词“car”。因此“car”是“car”的缩略语是没有二义性的，“car”不会被当成“carriage”或者任何在列表中以“car”开始的单词。 现在给你一组单词，要求找到所有单词唯一标识的最短前缀。 输入描述: 输入包含多组数据，每组数据第一行包含一个正整数n（2≤n≤1000）。紧接着n行单词，单词只有小写字母组成，长度不超过20个字符。 输出描述: 对应每一组数据，按照输入顺序依次输出每个单词的最短前缀。每组数据之后输出一个空格作为分隔。 输入例子: 3abaacb6carbohydratecartcarboniccariboucarriagecar 输出例子: abaaccarbohcartcarboncaricarrcar
#include
#include
#include
using namespace std;
char input[1010][22];
int n, len[1010], res[1010];
struct Node
{
vector
char val;
int cnt;
};
Node* root[30];
void fun(Node * curNode, int a, int b)
{
curNode->val = input[a][b];
curNode->cnt++;
b++;
if(b == len[a])
{
return;
}
else
{
bool ex = false;
for(int i = 0; i < curNode->child.size(); i++)
{
if(input[a][b] == curNode->child[i]->val)
{
ex = true;
fun(curNode->child[i], a, b);
break;
}
}
if(!ex)
{
Node *newNode = new Node();
newNode->cnt = 0;
fun(newNode, a, b);
curNode->child.push_back(newNode);
}
}
}
void find(Node * curNode, int a, int b)
{
if(curNode->cnt == 1)
{
printf("%c", curNode->val);
return;
}
else
{
printf("%c", curNode->val);
b++;
if(b == len[a])
{
return;
}
for(int i = 0; i < curNode->child.size(); i++)
{
if(input[a][b] == curNode->child[i]->val)
{
find(curNode->child[i], a, b);
break;
}
}
}
}
int main()
{
while(scanf("%d", &n) != EOF)
{
memset(res, 0, sizeof(res));
for(int i = 0; i < 26; i++)
{
root[i] = new Node();
root[i]->val = i + 'a';
root[i]->cnt = 0;
root[i]->child.clear();
}
for(int i = 0; i < n; i++)
{
scanf("%s", &input[i]);
len[i] = strlen(input[i]);
fun(root[input[i][0] - 'a'], i, 0);
}
for(int i = 0; i < n; i++)
{
find(root[input[i][0] - 'a'], i, 0);
printf("\n");
}
printf("\n");
}
return 0;
}
