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

字符串移位包含问题

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

【题目描述】

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

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

下一篇:生日

相关文章

【题解】光荣的梦想

【题目描述】Prince对他在这片大陆上维护的秩序感到满意,于是决定启程离开艾泽拉斯。在他动身之前,Prince决定赋予King_Bette最强大的能量以守护世界、保卫这里的平衡与和谐。在那个时代,平...

【题解】大数取模

【题目描述】求m%n。【输入描述】两个数,m和n。【输出描述】m模n的值。【样例输入】3【样例输出】2【数据范围】对于30%的数据, 1<m<10^18对于70%的数据, m>10^...

【题解】后缀表达式的值

【题解】后缀表达式的值

【题目描述】从键盘读入一个后缀表达式(字符串),只含有0-9组成的运算数及加(+)、减(—)、乘(*)、除(/)四种运算符。每个运算数之间用一个空格隔开,不需要判断给你的表达式是否合法。以@作为结束标...

【题解】求逆序对个数

【题目描述】有一实数序列A[1]、A[2] 、A[3] 、……A[n-1] 、A[n] (n<10000),若i<j,并且A[i]>A[j],则称A[i]与A[j]构成了一个逆序对,...

【题解】基因锁

【题目描述】小X终于意识到需要花大力气减重了,他询问了若干个减重专家后决定采用最适合年轻人的运动减重方案,考虑再三,小X最终选择了打羽毛球的方式,一个原因是小X的小伙伴大都喜欢打羽毛球,其次是打羽毛球...

线段

题目描述在一个数轴上有n条线段,现选取其中k条线段使得这k条线段两两没有重合部分,问最大的k为多少?输入格式第一行为一个正整数n,下面n行每行2个数字ai,bi,描述每条线段。输出格式输出文件仅包括1...