ptaR7-7重叠字符串

发布时间:2024年01月12日

题目

R7-7 重叠字符串

分数 10

全屏浏览题目

切换布局

作者?朱会东

单位?郑州轻工业大学

一个字符串经过一次重叠扩展之后长度变为原来的两倍,如果再进行重叠扩展会变成原来的四倍,例如:“AC”重叠扩展一次变成“ACAC” ,再进行扩展一次就变成了“ACACACAC”,现在给你一个字符串,请你判断这个字符串可能的最短原串是什么?

输入格式:

多实例,每个实例输入一行仅由英文字母组成的字符串,长度不大于1000。

输出格式:

对应每个实例输出最短原串和扩展次数。

输入样例:

ACMACM

输出样例:

ACM 1

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

思路

根据题上所介绍的,字符串是由不断复制进行的,我们可以通过不断地截断和更新,一旦发现两端不相等,那么就说明该字符串为最小折断,计数器的次数也就是重叠次数。

代码实现

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s,s1;
    int count;
    while(cin>>s){//输入字符串
        count=0;//计数器
        while(1){
            int l=s.size();
            if(l==1)break;//如果是一个字符重复
            s1=s.substr(0,l/2);//进行折断
            if(s1+s1==s){//如果拼接相等
                count++;
                s=s1;//更新字符串
            }
            else break;
        }
        cout<<s<<' '<<count<<endl;//输出
    }
}

总结

本题采用substr函数用来取字符串,如果用c语言代码的话会出现时间超限等问题,希望大家能多多理解c++理解stl容器,相信对以后的做题和理解都会有新的收获和认识。

尾声

本题采用substr函数截取字符串,对题目的理解和认识非常重要,如果觉得的笔者写的还不错的话,记得留下您的点赞收藏和关注哦~

文章来源:https://blog.csdn.net/2302_79862641/article/details/135550081
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。