当前位置：首页 > 题解目录 > 正文内容

字符串移位包含问题

亿万年的星光4年前 (2021-01-28)题解目录2872

【题目描述】

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

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

【输入格式】

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

【输出格式】

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

输出时每行末尾的多余空格，不影响答案正确性

【样例输入】

AABCD CDAA

【样例输出】

true

【题解】

一个错误代码：
测试点1 ：输入： 8 s8 正确输出：true
你的输出：false
测试点2：输入：

5XBmkALuGfBNumLs40luoG7P7Ae ymwRL77hKYRyOy15vhrCCoW3bWy

正确输出：false

#include<bits/stdc++.h>
using namespace std;
char s1[10000];
char s2[10000];
int zichuan(char longer[],char shorter[])//判断短的是不是长的子串
{
    int i,j,lenl,lens,s=0;
    lenl=strlen(longer);
    lens=strlen(shorter);
    for(i=0;i<lenl;i++)//这是判断从长字符串哪一位开始比较
    {
        for(j=0;j<lens;j++)//这是比较长度，等于短的长度，一位一位比
        {
            if(longer[i+j]==shorter[j]&amp;&amp;longer[i+j+1]==shorter[j+1])//判断是否连续相等
            {
                s++;
                //printf("s1[%d]=%c s2[%d]=%c s=%d\n",i+j,longer[i+j],j,shorter[j],s);
            }
        }
    }//因为最后一位是无法找到下一位也相等的，所以会少一个 
    if((s+1)==lens)//上述代码会导致计算中相同的字符数比实际相同的少1个，所以要加上一位
    return 1;
    else
    return 0;
}
int main()
{
    int i,j,k,len1,len2,ans,space;
    scanf("%s",s1);
    scanf("%s",s2);
    len1=strlen(s1);
    len2=strlen(s2);
    if(len1>=len2)//1长 
    {
        s1[0]=space;// 
        for(j=0;j<len1;j++)//多次位移，让整个字符串不断改变
        {
            for(i=0;i<len1-1;i++)
            {
                s1[i]=s1[i+1];//把第二个以后一次往前一位
                s1[len1-1]=space;//第一个给最后
            }
            ans=zichuan(s1,s2);
            //printf("s1=%s\n",s1);
            if(ans==1)
            {
                printf("true");
                return 0;
            }
            else if(j==len1-len2-1)
            {
                printf("false");
                return 0;
            }
        }
    }
    if(len2>len1)//2长 
    {
        s2[0]=space;
        for(j=0;j<len2;j++)
        {
            for(i=0;i<len2-1;i++)
            {
                s2[i]=s2[i+1];
                s2[len2-1]=space;
            }
            ans=zichuan(s2,s1);
            //printf("s2=%s\n",s2);
            if(ans==1)
            {
                printf("true");
                return 0;
            }
            else if(j==len2-len1-1)
            {
                printf("false");
                return 0;
            }
        }
    }
    return 0;
}