题解：CF2010C2 Message Transmission Error (hard version)

违规用户名1128255 · 2024-11-19 16:33:16 · 题解

题目大意

输入一个字符串，如果他是一个字符串重叠而成，则输出 YES ，并输出那个重叠的字符串，若无解输出 NO 。如果有多解输出其中一解即可。

思路

由于题目范围很小所以可以暴力枚举字符串的长度 len ，并且通过字符串的长度可以获得字符串中的第一个长度为 len 的子串，以及最后一个长度为 len 的子串。由于是是子串重叠，所以只需要判断这两个字符串即可。

Code

#include<bits/stdc++.h>
using namespace std;
string s;
int main()
{
    cin>>s;
    int len=s.size();//获取s的长度
    for(int t=1;t<len;t++)//枚举 
    {
        string x="",y="";//定义两个空串以备后面存储
        if((len+t)%2==0) //判断长度是否符合条件
        {
            for(int i=0;i<(len+i)/2;i++)//存储第一个字符串
            {
                x+=s[i];
            } 
            for(int i=len-(len+i)/2;i<len;i++)//存储第二个字符串
            {
                y+=s[i];
            }
            if(x==y)//如果相同就输出
            {
                cout<<"YES\n"<<x;//输出YES并输出其中一个字符串
                return 0;//有解后退出 
            } 
        }
    }
    cout<<"NO";//没有解就输出NO 
    return 0;
}