ZZULIOJ 1163: 亲和串（字符串）

题目描述

判断亲和串。亲和串的定义是这样的：给定两个字符串s1和s2,如果能通过s1循环移位，使s2包含在s1中，那么我们就说s2 是s1的亲和串。

输入

本题有多组测试数据，每组数据的第一行包含输入字符串s1,第二行包含输入字符串s2，s1与s2的长度均小于100000。

输出

如果s2是s1的亲和串，则输出"yes"，反之，输出"no"。每组测试的输出占一行。

样例输入 

AABCD
CDAA
ASD
ASDF
ab
aba

样例输出 

yes
no
no

 

tips:

1  在串1中（可循环）看串2是否是其子串

2  可以把串1改变为循环串（放在一个大的空间）

3   使用取余在原串1中进行查找

 

使用strcpy,strcat

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

int main(){
	int len1, len2,flag=0;
	char buf1[100001];
	char buf2[100001];
	char buf3[200002];
	while (scanf("%s%s",buf1,buf2)!=EOF)
	{
		len1 = strlen(buf1);
		len2 = strlen(buf2);
		if (len1<len2)
		{
			flag = 0;
		}
		else{
			strcpy(buf3,buf1);
			strcat(buf3,buf1);   //让串buf1在buf3中连成一个环
			if (strstr(buf3,buf2)!=NULL)  //串2找到返回位置，找不到返回NULL
			{
				flag =1 ;
			}
			else{
				flag = 0;
			}
		}

		if (flag)
		{
			printf("yes\n");
		}
		else{
			printf("no\n");
		}
	}
}

 

常规取余

#include<stdio.h>
#include<stdlib.h>

#include<string.h>
int main(){
	int len1, len2, flag;
	char buf1[100001];
	char buf2[100001];
	while (scanf("%s%s", buf1, buf2) != EOF)
	{
		len1 = strlen(buf1);
		len2 = strlen(buf2);
		if (len1<len2)
		{
			flag = 0;
		}
		else{
			for (int i = 0; i < len1; i++)
			{
				if (buf2[0] == buf1[i]){
					for (int j = 0; j < len2; j++)
					{
						if (buf2[j] == buf1[(i + j) % len1]){  //取余比较
							flag = 1;
						}
						else
						{
							flag = 0;
							break;
						}
					}
				}
				else  //串1的任何一个字符都不能和串2的首字符相等
				{
					flag = 0;
				}
				if (flag)
				{
					break;
				}
			}
		}

		if (flag)
		{
			printf("yes\n");
		}
		else{
			printf("no\n");
		}
	}
}