题目
Cpp
【问题描述】
字符环（来源：NOI题库）。有两个由字符构成的环，请写一个程序，计算这两个字符环上最长公共字符串的长度。例如，字符串“ABCEFAGADEGKABUVKLM”的首尾连在一起，构成一个环；字符串”MADJKLUVKL”的首尾连在一起，构成另一个环；“UVKLMA”是这两个环的一个公共字符串。
【输入格式】
有两行，每行一个不包含空格的字符串，每行的字符串首尾相连即为一个环。
【输出格式】
一行，输出一个整数，表示这两个字符环上最长公共字符串的长度。
【输入样例】
ABCEFAGADEGKABUVKLM MADJKLUVKL
【输出样例】
6
【数据范围】
字符串长度不超过255
分析
就是找两个字符串的最大的连续交集。只不过字符串首尾相连。
思路
其实要考虑的只不过是最后一位的下一位是第一位而已。这也很简单，直接将该字符串复制一份接到它后面即可。然后就可以循环找子集了。
代码
-
框架
int main(){ return 0; }
-
输入字符串
#include<cstdio> //scanf() char a[256], b[256]; int main(){ scanf("%s %s", &a, &b); return 0; }
-
拼接字符串
注意，不能直接用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; }
-
遍历字符串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; }
-
已经求出了一个字符串的子集，现在直接判断该子集是否同时存在于另一个字符串中。如果存在，就将该子集的长度比较存入变量中。
#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; }
-
最后，输出变量即可。
#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;
}
