stonechina0616

【题目描述】

最近国安人员截获了一份 RB 国的秘密情报， 全文都是经过加密的，每个单 词都很长。破译人员想到先把单词化简一下，方法是把每个单词尽量取短些的前 缀，但所取的前缀不能是其他单词的前缀。 这个任务现在就交给你来完成。 解释：“字符串 s1 是 s2 的前缀”是说把字符串 s2 的后面去掉某些，只保留 与 s1 相同长度是， s2 就与 s1 完全相同。如：“ abc“是” abcaade“和” abc“的 前缀，但不是” abadc“的前缀。 数据范围 单词数 N， 1<=n<=50; 每个单词长度不超过 50；并且都是由小写字母构成。 保证所给单词没有一个单词是另一个单词的前缀。

【输入文件 addreviate.in】

第一行一个整数 N，表示单词的个数。 下面有 N 行，每行一个单词。

【输出文件 addreviate.out】

共 N 行，每行一个单词，是对应上面 N 个单词化简后的单词。

【样例输入】 

样例测试点#1：

3

abc

efg

ijh

样例测试点#2：

3

aac

aad

aae

【样例输出】

样例测试点#1：

a

e

i

样例测试点#2：

aac

aad

aae

 对于每一个字符串i，枚举要截取的长度k，截出改字符串和其余的比较，看是否能够做其他字符串的前缀，如果都不能，那这个字符串就是字符串i的前缀。

代码：

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<string>

#define rep(q,p) for (int q=1;q<=p;q++)

using namespace std;

const int maxn=55;

int n,j;

string s[maxn],ts;

char tmp;

bool mark;

int main()

{

freopen("input.txt","r",stdin);

freopen("test.out","w",stdout);

cin>>n;

rep(i,n) cin>>s[i];

rep(i,n)

for (int k=1;k<s[i].length();k++)

{

mark=true;

ts=s[i].substr(0,k);

for (j=1;j<=n;j++)

if (i!=j && s[j].find(ts)==0)

{

mark=false;

break;

}

if (mark)

{

s[i][k]='0';

break;

}

}

rep(i,n)

{

for (int j=0;j<s[i].length();j++)

if (s[i][j]=='0') break;

else cout<<s[i][j];

cout<<endl;

}

return 0;

}