hdu2203亲和串（kmp+）

骑猪看日落 2022-08-21 09:38 134阅读 0赞

# 亲和串 #

**Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 11455    Accepted Submission(s): 5161**

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
      
       
      
       
        
       #include<stdio.h>
    #include<string.h>
    int next[100000];
    void NEW(char b[])
    {
        int i,q=0;
        next[0]=0;
        int m1;
        m1=strlen(b);
        for(i=1;i<m1;i++)
        {
            while(q>0&&b[q]!=b[i])
                q=next[q-1];
            if(b[q]==b[i])
                q++;
            next[i]=q;
        }
    }
    void xiao(char a[],char b[],int w)
    {
        int sum=0;
        int i;
        NEW(b);
        int q=0;
        int m=strlen(a);
        for(i=w;i<m;i++)
        {
            while(q>0&&a[i]!=b[q])
                q=next[q-1];
            if(a[i]==b[q])
            {
                q++;
            }
            //printf("%d\n",q);
            if(q==strlen(b))
            {
                printf("yes\n");
                return ;
            }
            sum++;
            if(sum==m-1)//判断是否访问完第一个子串。
                break;
            if(i==m-1)//让第一个子串形成环。
                i=-1;
        }
        printf("no\n");
    }
    int main()
    {
        char a[100000],b[100000];
        while(~scanf("%s %s",a,b))
        {
            int m,n,q,i;
            m=strlen(a);
            n=strlen(b);
            if(m>=n)
            {
                for(i=0;i<m;i++)
                    if(a[i]==b[0])//要想得到第二个字串肯定是第二个子串的第一个字母从第一个子串找出第一个子串。
                {
                    q=i;
                    break;
                }
                xiao(a,b,q);
            }
            else
                printf("no\n");
        }
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 HDU 1358(kmp)

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

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

相关 hdu2203亲和串（kmp+）

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

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

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

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

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

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

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

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

相关 HDU-2203

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

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

相关串匹配算法_KMP

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

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

相关 HDU - 2203 亲和串（KMP）

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

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

相关 HDU - 1358 Period (KMP)

Period Problem Description For each

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

相关 hdu 1686 KMP算法

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

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

相关 hdu 2040 亲和数

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

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