HDU - 2203 亲和串（KMP）

一时失言乱红尘 2022-05-19 06:48 176阅读 0赞

#                                               亲和串 #

### Problem Description ###

人随着岁数的增长是越大越聪明还是越大越笨，这是一个值得全世界科学家思考的问题,同样的问题Eddy也一直在思考，因为他在很小的时候就知道亲和串如何判断了，但是发现，现在长大了却不知道怎么去判断亲和串了，于是他只好又再一次来请教聪明且乐于助人的你来解决这个问题。  
亲和串的定义是这样的：给定两个字符串s1和s2,如果能通过s1循环移位，使s2包含在s1中，那么我们就说s2 是s1的亲和串。

### Input ###

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

### Output ###

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

### Sample Input ###

AABCD

CDAA

ASD

ASDF

### Sample Output ###

yes

no

**题意描述：**  
判断两个字符串s1,s2是否满足s1通过循环移位包含s2.

**解题思路：**

利用kmp当循环查找当查到相同时标记，跳出循环；当i=lena时即i将主串走过一遍后，i=0从头继续查找实现循环移位，当第二遍i又找到lena时结束跳出循环，若还没有出现子串，输出no;

#include<stdio.h>
    #include<string.h>
    int main()
    {
    	char a[100010],b[100010];
    	int lena,lenb,i,j,next[100010],flag,h;
    	while(gets(a)!=NULL)
    	{
    		gets(b);
    		lena=strlen(a);
    		lenb=strlen(b);
    		j=0;
    		next[0]=0;
    		//求出b的next[]数组 
    		for(i=1;i<=lenb-1;)
    		{
    			if(j==0&&b[i]!=b[j])
    			{
    				next[i]=0;
    				i++;
    			}
    			if(b[i]==b[j])
    			{
    				next[i]=j+1;	
    				i++;
    				j++;
    			}
    			if(j>0&&b[i]!=b[j])
    			{
    				j=next[j-1];
    			}
    		}
    		flag=0;
    		h=0;
    		for(i=0,j=0;;)
    		{
    			if(a[i]==b[j])
    			{
    				j++;
    				if(j==lenb)
    				{
    					flag=1;
    					break;
    				}
    				i++;
    			}
    			if(h==1&&i==lena)//第二次又查找完时，结束循环 
    				break;
    			
    			if(h==0&&i==lena)//当第一次字符串a查完时，i变为0 
    			{
    				i=0;
    				h=1;
    			}
    			
    			if(j==0&&a[i]!=b[j])
    				i++;
    				
    			//因在循环中又两个i++,在哪个后边查找完都有可能所以判断了两次 
    			if(h==0&&i==lena)//当第一次字符串a查完时，i变为0 
    			{
    				i=0;
    				h=1;
    			}
    			if(j>0&&a[i]!=b[j])
    				j=next[j-1];
    		}
    		if(flag==1)
    			printf("yes\n");
    		else
    			printf("no\n");
    	}
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，176人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 1358(kmp)

题意：给出一个数字n，接下来一行是一个字符串，n是这个字符串的长度。求这个字符串的所有是循环字符串的前缀。 kmp中的next数组只得是第i个字符匹配错误，向前跳的位置nex

叁歲伎倆/ 2022年09月20日 12:44/ 0 赞/ 31 阅读

相关 hdu2203亲和串（kmp+）

亲和串 Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Other

骑猪看日落/ 2022年08月21日 09:38/ 0 赞/ 148 阅读

相关 1163: 亲和串（字符串）

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

缺乏、安全感/ 2022年06月11日 04:42/ 0 赞/ 184 阅读

相关 HDU-2203-亲和串-kmp算法

亲和串 Problem Description 人随着岁数的增长是越大越聪明还是越大越笨，这是一个值得全世界科学家思考的问题,同样的问题E

客官°小女子只卖身不卖艺/ 2022年06月05日 05:30/ 0 赞/ 185 阅读

相关 HDU-2203

亲和串 Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Other

￡神魔★判官ぃ/ 2022年05月27日 11:26/ 0 赞/ 159 阅读

相关串匹配算法_KMP

串匹配串匹配问题即是：如何在字符串数据中，检测和提取以字符串形式给出的某一局部特征一般的，即： -------------------- 对基于同一字符表的任何文本

偏执的太偏执、/ 2022年05月21日 05:52/ 0 赞/ 249 阅读

相关 HDU - 2203 亲和串（KMP）

亲和串 Problem Description 人随着岁数的增长是越大越

一时失言乱红尘/ 2022年05月19日 06:48/ 0 赞/ 177 阅读

相关 HDU - 1358 Period (KMP)

Period Problem Description For each

灰太狼/ 2022年05月18日 20:45/ 0 赞/ 198 阅读

相关 hdu 1686 KMP算法

题意：　　求子串w在T中出现的次数。 kmp算法详解：http://www.cnblogs.com/XDJjy/p/3871045.html ![ContractedB

╰+哭是因爲堅強的太久メ/ 2022年01月06日 21:33/ 0 赞/ 209 阅读

相关 hdu 2040 亲和数

hdu 2040 亲和数题意题解源代码 [传送门][Link 1] 题意给定两个整数n,m，n的真约数和等于m,m的真约

快来打我*/ 2021年10月13日 02:49/ 0 赞/ 226 阅读