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

字符串移位包含问题

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

【题目描述】

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

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

【输入格式】

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

【输出格式】

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

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

【样例输入】

AABCD CDAA

【样例输出】

true

【题解】

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

测试点2:输入:

5XBmkALuGfBNumLs40luoG7P7Ae ymwRL77hKYRyOy15vhrCCoW3bWy

正确输出:false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#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;
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:
返回列表

上一篇:第n小质数

下一篇:生日

相关文章

【题解】感应门

【题目描述】感应门会在有人经过的时候自动打开,冷却d 秒后自动关闭。如果有人在感应门打开的状态下通过,那么冷却时间会重置,重新冷却d秒后再关闭。在一段时间内,有 n个人陆续通过了感应门,他们...

绝对素数

【题目描述】如果一个自然数是素数,且它的数字位置经过对换后仍为素数,则称为绝对素数,例如13。试求出所有二位绝对素数。【输入描述】无【输出描述】所有二位绝对素数(由小到大,一个数一行)。【输入样例】无...

合影效果

【题目描述】小云和朋友们去爬香山,为美丽的景色所陶醉,想合影留念。如果他们站成一排,男生全部在左(从拍照者的角度),并按照从矮到高的顺序从左到右排,女生全部在右,并按照从高到矮的顺序从左到右排,请问他...

【题解】区间和

1.区间和(sum.cpp)【描述】输入一个整数Q,进行Q次询问,每次给定两个整数l和r,每一次输出l~r中所有平方数的和 % 1000000007【输入】第一行是一个整数Q后面的Q行每行有...

【题解】大整数加法

【题目描述】求两个不超过200位的非负整数的和。【输入】有两行,每行是一个不超过200位的非负整数,可能有多余的前导0。【输出】一行,即相加后的结果。结果里不能有多余的前导0,即如果结果是342,那么...

【题解】连通块

【题目描述】一个n × m的方格图,一些格子被涂成了黑色,在方格图中被标为1,白色格子标为0。问有多少个四连通的黑色格子连通块。四连通的黑色格子连通块指的是一片由黑色格子组成的区域,其中的每个黑色格子...