題目

Cpp
【問題描述】
字符環（來源：NOI題庫）。有兩個由字符構成的環，請寫一個程序，計算這兩個字符環上最長公共字符串的長度。例如，字符串“ABCEFAGADEGKABUVKLM”的首尾連在一起，構成一個環；字符串”MADJKLUVKL”的首尾連在一起，構成另一個環；“UVKLMA”是這兩個環的一個公共字符串。
【輸入格式】
有兩行，每行一個不包含空格的字符串，每行的字符串首尾相連即為一個環。
【輸出格式】
一行，輸出一個整數，表示這兩個字符環上最長公共字符串的長度。
【輸入樣例】
ABCEFAGADEGKABUVKLM MADJKLUVKL
【輸出樣例】
6
【數據范圍】
字符串長度不超過255

---

分析

就是找兩個字符串的最大的連續交集。只不過字符串首尾相連。

---

思路

其實要考慮的只不過是最后一位的下一位是第一位而已。這也很簡單，直接將該字符串復制一份接到它后面即可。然后就可以循環找子集了。

---

代碼

0. 框架

   int main(){return 0;
   }
   

   ---

1. 輸入字符串

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

   ---

2. 拼接字符串
   注意，不能直接用strcat()函數拼接！

   #include<cstdio>	//scanf()
   #include<cstring>	//strcpy(), strcat(), memset()
   char a[256], b[256], c[256];
   int main(){scanf("%s %s", &a, &b);strcpy(c, a);strcat(a, c);memset(c, 0, sizeof(c));strcpy(c, b);strcat(b, c);return 0;
   }
   

   ---

3. 遍歷字符串a的子集（遍歷頭和尾，并同時求出子集）。詳見該文張2.5版解題思路

   #include<cstdio>	//scanf()
   #include<cstring>	//strcpy(), strcat(), memset(), strlen()
   char a[256], b[256]， c[256];
   int l;
   int main(){scanf("%s %s", &a, &b);strcpy(c, a);strcat(a, c);memset(c, 0, sizeof(c));strcpy(c, b);strcat(b, c);l=strlen(a);for(int i=0; i<l; i++){memset(c, 0, sizeof(c));for(int j=0; j<l-i; j++){c[j]=a[i+j];}}return 0;
   }
   

   ---

4. 已經求出了一個字符串的子集，現在直接判斷該子集是否同時存在于另一個字符串中。如果存在，就將該子集的長度比較存入變量中。

   #include<cstdio>	//scanf()
   #include<cstring>	//strcpy(), strcat(), memset(), strlen(), strstr()
   #include<cmath>		//fmax()
   char a[256], b[256], c[256];
   int l, ans;
   int main(){scanf("%s %s", &a, &b);strcpy(c, a);strcat(a, c);memset(c, 0, sizeof(c));strcpy(c, b);strcat(b, c);l=strlen(a);for(int i=0; i<l; i++){memset(c, 0, sizeof(c));for(int j=0; j<l-i; j++){c[j]=a[i+j];if(strstr(b, c)!=NULL){ans=fmax(ans, j+1);}}}return 0;
   }
   

   ---

5. 最后，輸出變量即可。

   #include<cstdio>	//scanf(), printf()
   #include<cstring>	//strcpy(), strcat(), memset(), strlen(), strstr()
   #include<cmath>		//fmax()
   char a[256], b[256], c[256];
   int l, ans;
   int main(){scanf("%s %s", &a, &b);strcpy(c, a);strcat(a, c);memset(c, 0, sizeof(c));strcpy(c, b);strcat(b, c);l=strlen(a);for(int i=0; i<l; i++){memset(c, 0, sizeof(c));for(int j=0; j<l-i; j++){c[j]=a[i+j];if(strstr(b, c)!=NULL){ans=fmax(ans, j+1);}}}printf("%d", ans);return 0;
   }
   

   ---

---

答案

#include<cstdio>
#include<cstring>
#include<cmath>
char a[256], b[256], c[256];
int l, ans;
int main(){scanf("%s %s", &a, &b);strcpy(c, a);strcat(a, c);memset(c, 0, sizeof(c));strcpy(c, b);strcat(b, c);l=strlen(a);for(int i=0; i<l; i++){memset(c, 0, sizeof(c));for(int j=0; j<l-i; j++){c[j]=a[i+j];if(strstr(b, c)!=NULL){ans=fmax(ans, j+1);}}}printf("%d", ans);return 0;
}

---