【C++】每周一题——2024.3.3

题目

Cpp
【问题描述】
字符环（来源：NOI题库）。有两个由字符构成的环，请写一个程序，计算这两个字符环上最长公共字符串的长度。例如，字符串“ABCEFAGADEGKABUVKLM”的首尾连在一起，构成一个环；字符串”MADJKLUVKL”的首尾连在一起，构成另一个环；“UVKLMA”是这两个环的一个公共字符串。
【输入格式】
有两行，每行一个不包含空格的字符串，每行的字符串首尾相连即为一个环。
【输出格式】
一行，输出一个整数，表示这两个字符环上最长公共字符串的长度。
【输入样例】
ABCEFAGADEGKABUVKLM MADJKLUVKL
【输出样例】
6
【数据范围】
字符串长度不超过255

---

分析

就是找两个字符串的最大的连续交集。只不过字符串首尾相连。

---

思路

其实要考虑的只不过是最后一位的下一位是第一位而已。这也很简单，直接将该字符串复制一份接到它后面即可。然后就可以循环找子集了。

---

代码

0. 框架

   int main(){
   	return 0;
   }
   1
   2
   3

   ---

1. 输入字符串

   #include	//scanf()
   char a[256], b[256]; 
   int main(){
   	scanf("%s %s", &a, &b);
   	return 0;
   }
   1
   2
   3
   4
   5
   6

   ---

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

   #include	//scanf()
   #include	//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;
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12

   ---

3. 遍历字符串a的子集（遍历头和尾，并同时求出子集）。详见该文张2.5版解题思路

   #include	//scanf()
   #include	//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;
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20

   ---

4. 已经求出了一个字符串的子集，现在直接判断该子集是否同时存在于另一个字符串中。如果存在，就将该子集的长度比较存入变量中。

   #include	//scanf()
   #include	//strcpy(), strcat(), memset(), strlen(), strstr()
   #include		//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;
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24

   ---

5. 最后，输出变量即可。

   #include	//scanf(), printf()
   #include	//strcpy(), strcat(), memset(), strlen(), strstr()
   #include		//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;
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25

   ---

---

答案

#include
#include
#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

---