ptaR7-7重叠字符串

题目

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函数截取字符串，对题目的理解和认识非常重要，如果觉得的笔者写的还不错的话，记得留下您的点赞收藏和关注哦~