【C++】每周一题——2024.3.3（手滑再再写一篇）
题目
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个字符串中的最大公共子串。
思路
先遍历出其中两个字符串的所有公共子集，然后后面每输入一个字符串就排除掉几个不存在当中的，最后找出最长的输出。
代码
-
框架
int main(){return 0; }
-
先输入前两个字符串。
#include<cstdio> //scanf() char a[256], b[256]; int main(){scanf("%[^\n]\n%[^\n]", &a, &b);return 0; }
-
找出这两个字符串的公共子串。详情可见这篇。
#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：代表所有公共子串的数量。
-
输入剩下的字符串，边输入一边删除不存在的子串。记得修改变量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; }
-
找出公共子串中，最长的子串，并输出。
#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;
}