破译情报-NOIP2016提高组复赛模拟试题

时间:2022-10-03 19:07:38

【题目描述】

最近国安人员截获了一份 RB 国的秘密情报, 全文都是经过加密的,每个单 词都很长。破译人员想到先把单词化简一下,方法是把每个单词尽量取短些的前 缀,但所取的前缀不能是其他单词的前缀。 这个任务现在就交给你来完成。

解释:“字符串s1s2的前缀”意思是把字符串s2的后面去掉某些字符,只保留与s1相同长度的子串,则s1就称为s2的前缀。如: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

 

思路:这题算是送分题中的高难度题了,对于各位高手来说不是什么问题,我说这题是为了提一下一个库函数,这个库函数是我们一般不经常用的,废话不多说,我先从头讲起吧

这题要求我们保留n个字符串的前缀,使得这些前缀和其他前缀不相同,缩小存储空间,看起来很简单,其实还是有点复杂滴

 例如题目中给的样例:破译情报-NOIP2016提高组复赛模拟试题可以先把第一个字符按照图中红线分段,提取第一行第一个字符,来和下面的每一个字符串进行对比破译情报-NOIP2016提高组复赛模拟试题,如果这个段并不在下面任何一个字符串中是前缀,就可以在后面加上个'\0'表示截取这一段

之后对每一行都采取这样的措施,就可以实现保留前缀

 

代码如下:

 

 1 #include <stdio.h>
2 #include <string.h>
3 int main()
4 {
5 //freopen("addreviate.in","r",stdin);
6 //freopen("addreviate.out","w",stdout);
7 char a[51][51],temp;
8 int n;
9 int i,j,k;
10 int flag,len;
11 scanf("%d",&n);
12 for(i=0;i<n;i++)
13 {
14 scanf("%s",a[i]);
15 }
16 for(i=0;i<n;i++)
17 {
18 len=strlen(a[i]);//测一下a[i]的长度
19 for(k=1;k<len;k++)//扫描整个子串
20 {
21 temp=a[i][k];//记录一下当前字符
22 a[i][k]='\0';//当前标记为空
23 for(j=0;j<n;j++)
24 {
25 if(i!=j&&(strstr(a[j],a[i])-a[j])==0)//如果不是同一行,并且这个子串与这个字符串的前面一部分吻合,就可以停止了
26 {
27 break;//停止!!
28 }
29 }
30 if(j>=n)//这个空的位置前面一段保证前缀不重复,就可以标记为空了
31 {
32 a[i][k]='\0';
33 break;
34 }
35 else//否则还要还原回去,继续寻找下一位
36 {
37 a[i][k]=temp;
38 }
39 }
40 }
41 for(i=0;i<n;i++)
42 {
43 printf("%s\n",a[i]);
44 }
45 return 0;
46 }