題目

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;
}

---