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

字符串移位包含问题

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

【题目描述】

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

给定两个字符串 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小质数

下一篇:生日

相关文章

质数环

【题目描述】有一个整数n,把从1到n的数字无重复的排列成环,且使每相邻两个数(包括首尾)的和都为素数,称为素数环。为了简便起见,我们规定每个素数环都从1开始。例如,下面就是6的一个素数环。1 4 3...

【题解】开关灯(1)

【题目描述】假设有N盏灯(N为不大于5000的正整数),从1到N按顺序依次编号,初始时全部处于开启状态;有M个人(M为不大于N的正整数)也从1到M依次编号。第一个人(1号)将灯全部关闭,第二个人(2号...

【题解】Best Cow Fences

【题目描述】    给定一个长度为n的正整数序列A。求一个平均数最大的,长度不小于L的子序列。【输入描述】第一行,n和L;n个正整数,表示A。【输出描述】&nb...

【题解】营救巨轮

【题目描述】一艘远洋巨轮在大海中遇到故障,船长库克立刻发出了求救信号。距离最近的辽宁号收到了讯息,时间就是生命,必须尽快赶到那里。通过侦测,辽宁号获取了一张海洋图。这张图将海洋部分分化成n*n个比较小...

【题解】剔除相关数

【题目描述】一个数与另一个数如果含有相同数字和个数的字符,则称两数相关。现有一堆乱七八糟的整数,里面可能充满了彼此相关的数,请你用一下手段,自动地将其剔除。【输入描述】每组数据前有一个N(<10...

字符全排列

【题目描述】给定一个由不同的小写字母组成的字符串,输出这个字符串的所有全排列。我们假设对于小写字母有‘a’ <‘b’ < … <‘y’<‘z’,而且给定的字符串中的字母已经按照...