Chinaunix首页 | 论坛 | 博客
  • 博客访问: 506058
  • 博文数量: 65
  • 博客积分: 1158
  • 博客等级: 少尉
  • 技术积分: 1261
  • 用 户 组: 普通用户
  • 注册时间: 2012-07-18 22:07
文章分类

全部博文(65)

文章存档

2016年(1)

2014年(2)

2013年(9)

2012年(53)

分类: C/C++

2012-10-25 16:42:26

/**
Description
给你K个字符串,请求出它们的最长公共前缀。
输入第一行是一个整数N,表示测试样例的个数。
每个测试样例的第一行是一个整数K(2 <= k <= 20),表示有多少个字符串;
以后每行是一个字符串,每个字符串的长度不超过200个字符。
输出每行输出一个样例的结果。先输出“Case #: ”,其中’#’为样例的序号(从1开始),
冒号为英文冒号,后接一个空格;然后是对应样例的结果。
如果没有公共前缀,则无需输出前缀,但Case信息仍需要输出。

Sample Input

2
3
ACD
ACDEF
ACDFE
2
ABC
BCD


Sample Output

Case 1: ACD
Case 2:

*/


点击(此处)折叠或打开

  1. #include<stdio.h>
  2. #include<string.h>
  3. #define MAX1 25
  4. #define MAX2 210

  5. void getPrefix(char input[][MAX2],int k);
  6. int main()
  7. {
  8.     int cases,k,i,j,count = 0;//cases个测试用例、每个用例k个串、count表示要输出第几个的用例
  9.     char input[MAX1][MAX2];

  10.     scanf("%d",&cases);

  11.     while(getchar() != '\n');

  12.     while(cases--)
  13.     {
  14.         count++;
  15.         i = 0;
  16.         scanf("%d",&k);

  17.         while(getchar() != '\n');

  18.         j = k;
  19.         while(j--)
  20.         {
  21.             gets(input[i]);
  22.             i++;
  23.         }

  24.         printf("Case %d: ",count);
  25.         getPrefix(input,k);
  26.     }
  27.     return 0;
  28. }

  29. void getPrefix(char input[][MAX2],int k)
  30. {
  31.     int i,minLength = 10000,temp,j;
  32.     bool flag = false;

  33.     //求得最小串长
  34.     for(i=0;i<k;i++)
  35.     {
  36.         temp = strlen(input[i]);
  37.         if(temp < minLength)
  38.         {
  39.             minLength = temp;
  40.         }
  41.     }


  42.     for(i=0;i<minLength;i++)
  43.     {
  44.         for(j=0;j<k-1;j++)
  45.         {
  46.             if(input[j][i] == input[j+1][i])
  47.             {
  48.                 continue;
  49.             }
  50.             else
  51.             {
  52.                 flag = true;
  53.                 break;
  54.             }
  55.         }

  56.         if(!flag)
  57.         {
  58.             printf("%c",input[j][i]);
  59.         }
  60.     }

  61.     printf("\n");
  62. }


阅读(1137) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~