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

【题目描述】

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

解释：“字符串s₁是s₂的前缀”意思是把字符串s₂的后面去掉某些字符，只保留与s₁相同长度的子串，则s₁就称为s₂的前缀。如：“abc”是“abcaade”和“abc”的前缀，但不是“abadc”的前缀。

数据范围单词数 N， 1<=n<=50; 每个单词长度不超过 50；并且都是由小写字母构成。保证所给单词没有一个单词是另一个单词的前缀。

【输入文件 addreviate.in】

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

【输出文件 addreviate.out】

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

【样例输入】

样例测试点#1：

abc

efg

ijh

样例测试点#2：

aac

aad

aae

【样例输出】

样例测试点#1：

样例测试点#2：

aac

aad

aae

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

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

例如题目中给的样例：可以先把第一个字符按照图中红线分段，提取第一行第一个字符，来和下面的每一个字符串进行对比，如果这个段并不在下面任何一个字符串中是前缀，就可以在后面加上个'\0'表示截取这一段

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

代码如下：

 #include <stdio.h>

 #include <string.h>

 int main()

 {

     //freopen("addreviate.in","r",stdin);

     //freopen("addreviate.out","w",stdout);

     char a[][],temp;

     int n;

     int i,j,k;

     int flag,len;

     scanf("%d",&n);

     for(i=;i<n;i++)

     {

         scanf("%s",a[i]);

     }

     for(i=;i<n;i++)

     {

         len=strlen(a[i]);//测一下a[i]的长度

         for(k=;k<len;k++)//扫描整个子串

         {

             temp=a[i][k];//记录一下当前字符

             a[i][k]='\0';//当前标记为空

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

             {

                 if(i!=j&&(strstr(a[j],a[i])-a[j])==)//如果不是同一行，并且这个子串与这个字符串的前面一部分吻合，就可以停止了

                 {

                     break;//停止！！

                 }

             }

             if(j>=n)//这个空的位置前面一段保证前缀不重复，就可以标记为空了

             {

                 a[i][k]='\0';

                 break;

             }

             else//否则还要还原回去，继续寻找下一位

             {

                 a[i][k]=temp;

             }

         }

     }

     for(i=;i<n;i++)

     {

         printf("%s\n",a[i]);

     }

     return ;

 }

巴特西

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

最新文章

热门文章