北京网站制作net2006搜狐财经峰会直播

题目

Cpp
【问题描述】
求N个字符串的最长公共子串，2 < N＜＝20，字符串长度不超过255。
例如：N＝3，由键盘依次输入三个字符串为
What is local bus?
Name some local buses.
local bus is a high speed I/O bus close to the processer.
则最长公共子串为"local bus"。

分析

找n个字符串中的最大公共子串。

思路

先遍历出其中两个字符串的所有公共子集，然后后面每输入一个字符串就排除掉几个不存在当中的，最后找出最长的输出。

代码

0. 框架

   int main(){return 0;
   }
   

   ---

1. 先输入前两个字符串。

   #include<cstdio>	//scanf()
   char a[256], b[256];
   int main(){scanf("%[^\n]\n%[^\n]", &a, &b);return 0;
   }
   

   ---

2. 找出这两个字符串的公共子串。详情可见这篇。

   #include<cstdio>	//scanf()
   #include<cstring>	//strlen(), memset(), strstr(), strcpy()
   char a[256], b[256], t[256], c[256*256][256];
   int x;
   int main(){scanf("%[^\n]\n%[^\n]", &a, &b);for(int i=0; i<strlen(a); i++){memset(t, 0, sizeof(t));for(int j=0; j<strlen(a)-i; j++){t[j]=a[i+j];if(strstr(b, t)!=NULL){strcpy(c[x], t);x++;}}}return 0;
   }
   

   数组t：临时用，存放当前遍历到的子串。
   二维数组c：存放遍历到的所有公共子串。
   整形变量x：代表所有公共子串的数量。

   ---

3. 输入剩下的字符串，边输入一边删除不存在的子串。记得修改变量x。

   #include<cstdio>	//scanf()
   #include<cstring>	//strlen(), memset(), strstr(), strcpy()
   char a[256], b[256], t[256], c[256*256][256];
   int x;
   int main(){scanf("%[^\n]\n%[^\n]", &a, &b);for(int i=0; i<strlen(a); i++){memset(t, 0, sizeof(t));for(int j=0; j<strlen(a)-i; j++){t[j]=a[i+j];if(strstr(b, t)!=NULL){strcpy(c[x], t);x++;}}}while(scanf("\n%[^\n]", &b)!=EOF){for(int i=x-1; i>=0; i--){if(strstr(b, c[i])==NULL){for(int j=i; j<x; j++){strcpy(c[i], c[i+1]);}x--;}}}return 0;
   }
   

   ---

4. 找出公共子串中，最长的子串，并输出。

   #include<cstdio>	//scanf(), printf()
   #include<cstring>	//strlen(), memset(), strstr(), strcpy()
   char a[256], b[256], t[256], c[256*256][256];
   int x;
   int main(){scanf("%[^\n]\n%[^\n]", &a, &b);for(int i=0; i<strlen(a); i++){memset(t, 0, sizeof(t));for(int j=0; j<strlen(a)-i; j++){t[j]=a[i+j];if(strstr(b, t)!=NULL){strcpy(c[x], t);x++;}}}while(scanf("\n%[^\n]", &b)!=EOF){for(int i=x-1; i>=0; i--){if(strstr(b, c[i])==NULL){for(int j=i; j<x; j++){strcpy(c[i], c[i+1]);}x--;}}}memset(a, 0, sizeof(a));for(int i=0; i<x-1; i++){if(strlen(c[i])>strlen(a)){strcpy(a, c[i]);}}printf("%s", a);return 0;
   }
   

   ---

答案

#include<cstdio>	//scanf(), printf()
#include<cstring>	//strlen(), memset(), strstr(), strcpy()
char a[256], b[256], t[256], c[256*256][256];
int x;
int main(){scanf("%[^\n]\n%[^\n]", &a, &b);for(int i=0; i<strlen(a); i++){memset(t, 0, sizeof(t));for(int j=0; j<strlen(a)-i; j++){t[j]=a[i+j];if(strstr(b, t)!=NULL){strcpy(c[x], t);x++;}}}while(scanf("\n%[^\n]", &b)!=EOF){for(int i=x-1; i>=0; i--){if(strstr(b, c[i])==NULL){for(int j=i; j<x; j++){strcpy(c[i], c[i+1]);}x--;}}}memset(a, 0, sizeof(a));for(int i=0; i<x-1; i++){if(strlen(c[i])>strlen(a)){strcpy(a, c[i]);}}printf("%s", a);return 0;
}