欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

OpenJ_Bailian - 3711 字符串移位包含问题(模拟 + 简单解法)

程序员文章站 2022-04-30 22:49:56
...
  • 字符串移位包含问题

对于一个字符串来说,定义一次循环移位操作为:将字符串的第一个字符移动到末尾形成新的字符串。

给定两个字符串s1和s2,要求判定其中一个字符串是否是另一字符串通过若干次循环移位后的新字符串的子串。例如CDAA是由AABCD两次移位后产生的新串BCDAA的子串,而ABCD与ACBD则不能通过多次移位来得到其中一个字符串是新串的子串。

  • Input

一行,包含两个字符串,中间由单个空格隔开。字符串只包含字母和数字,长度不超过30。

  • Output

如果一个字符串是另一字符串通过若干次循环移位产生的新串的子串,则输出true,否则输出false。

  • Sample Input

AABCD CDAA

  • Sample Output

true

虽然题目简单,但还是要注意判断两个字符的长度,因为并不知道子串是哪个
第一种解法是模拟,就不说了,直接看代码,自己体会吧

#include<cstdio>
#include<cstring>

using namespace std;

int main(){
	char str1[31], str2[31], tmp[31];
	scanf("%s %s", str1, str2);
	
	int s1 = strlen(str1);
	int s2 = strlen(str2);
	if(s1 < s2){
		int x;
		tmp[31] = str1[31];
		str1[31] = str2[31];
		str2[31] = tmp[31];
		x=s1;
		s1=s2;
		s2=x;
	}
    int i, j;
	for(i=0; i < s1; i++){
		for(j=0; j < s2; j++){
			if(str1[(i + j) % s1] != str2[j])
				break;
		}
		if(j==s2)
			break; 
	}
	if(j==s2)
		printf("true\n");
	else 
		printf("false\n");
	return 0;
}

第二种就是利用字符串函数解,首先我们可以肯定长的字符串肯定不是子串,我们将长的字符串如样例中的AABCD后面再加AABCD,这样就变成了AABCDAABCD,显然AABCD任何循环移位的子串都在这个里面,然后我们再用strstr函数在AABCDAABCD中查找CDAA,如果找不到就输出false,如果找到了就输出true。
但是这个代码并RE了,我猜会不会是它并不想让我们用字符串函数来写这道题,而是想锻炼我们处理字符串的能力?或者就是我的问题吧。
代码如下:

#include <stdio.h>
#include <string.h>


int main()
{
	char str1[100], str2[100];
	scanf("%s %s", str1, str2);
	if(strlen(str1) < strlen(str2))
	{
		char tmp[100];
		strcpy(tmp, str1);
		strcpy(str1, str2);
		strcpy(str2, tmp);
	}
	strncat(str1, str1, 100);
	if(strstr(str1, str2) == NULL) printf("false");
	else printf("true");
	return 0;
} 

后面没用函数,直接手打实现这些函数的功能提交AC了,果然不是我的问题
OpenJ_Bailian - 3711 字符串移位包含问题(模拟 + 简单解法)
实现代码如下

#include <stdio.h>
#include <string.h>


int main()
{
	char str1[100], str2[100];
	scanf("%s %s", str1, str2);
	int len1 = strlen(str1), len2 = strlen(str2);
	if(len1 < len2)
	{
		char tmp[100];
		for(int i = 0; i < len1; i++)
			tmp[i] = str1[i];
		for(int i = 0; i < len2; i++)
			str1[i] = str2[i];
		for(int i = 0; i < len1; i++)
			str2[i] = tmp[i];
		int len;
		len = len1;
		len1 = len2;
		len2 = len;
	}
	int j;
	for(int i = 0; i < len1; i++) str1[i + len1] = str1[i];
	for(int i = 0; i < len1 * 2 - 1; i++)
	{
		for(j = 0; j < len2; j++)
			if(str1[i + j] != str2[j] )  break;
		if(j == len2) break;
	}
	if(len2 == j) printf("true");
	else printf("false");
	return 0;
} 

后面又试了一下,发现是strcat这个函数有问题,建议大家以后也少用这个函数。 OpenJ_Bailian - 3711 字符串移位包含问题(模拟 + 简单解法)

#include <stdio.h>
#include <string.h>


int main()
{
	char str1[100], str2[100];
	scanf("%s %s", str1, str2);
	if(strlen(str1) < strlen(str2))
	{
		char tmp[100];
		strncpy(tmp, str1, 100);
		strncpy(str1, str2, 100);
		strncpy(str2, tmp, 100);
	}
	int len = strlen(str1);
	for(int i = 0; i < len; i++) str1[i + len] = str1[i];
	if(strstr(str1, str2) == NULL) printf("false");
	else printf("true");
	return 0;
} 

End