上海计算机学会2020年11月月赛C++乙组T1还原字符串
发布时间
阅读量：
阅读量
题目描述
假设存在一个小写字母串s。通过生成一份副本并将其与原串连接起来，则会形成一个长度加倍的新串s⋅s。随后，在该双倍长度的串中选择一个中间位置并添加一个新的小写字母c，则会生成一个新的字母串t。
给定 t，请找出它对应的 s，若这样的 s 有多种可能，则输出 s 的全部可能。
输入格式
单个字符串 t，保证都是小写英文字母，且 t 的长度为奇数。
输出格式
如果没有，则返回 No\ solution；如果只有一个可能性，则返回该字符串；如果有多个可能性，则优先输出字典序靠前的字符串，并用换行符隔开
数据范围
设 n 为字符串 t 的长度，
- 对于30%的数据，n≤21；
- 对于60%的数据，n≤5001；
- 对于100%的数据，3≤n≤5000001。
样例数据
输入:
abcdabc
输出:
abc
输入:
abcde
输出:
No solution
输入:
ababa
输出:
ab
ba
解析：分两种情况讨论，即插入的字符在左边还是在右边
两个字符串只有一个字符不同，则成立；
如果左右两边都成立，证明则可能有两种情况，分别判断。
详见代码：
#include <bits/stdc++.h>
using namespace std;
string s;
bool pd(string l, string r) {//判断左右两边是否只差一个字符，短的放左边
int lp = 0, rp = 0;
int lenl, lenr;
lenl = l.size();
lenr = r.size();
int b = 0;
while (lp <= lenl - 1 && rp <= lenr - 1) {
if (l[lp] != r[rp]) {
rp++;
b++;
if (b > 1) return false;
} else {
lp++;
rp++;
}
}
return true;
}
int main() {
cin >> s;
int len, m;
string a1, a2, b1, b2;
len = s.length();
m = len / 2;
a1 = s.substr(0, m);//按左小右大拆分成a1 a2
a2 = s.substr(m, m + 1);
b1 = s.substr(0, m + 1);//按左大右小拆分成b1 b2
b2 = s.substr(m + 1, m);
bool t1, t2;
t1 = pd(a1, a2);//分别判断
t2 = pd(b2, b1);
if (t1 && t2) {//都成立，比较大小，按先小后大顺序输出
if (a1 < b2) {
cout << a1 << endl;
cout << b2 << endl;
} else if (a1 > b2) {
cout << b2 << endl;
cout << a1 << endl;
} else {//相同证明只有一种可能
cout << a1 << endl;
}
} else if (t1) {//只有第一种拆分成立的情况
cout << a1 << endl;
} else if (t2) {//只有第二种拆分成立的情况
cout << b2 << endl;
} else {//两种拆分都不成立的情况
cout << "No solution" << endl;
}
return 0;
}全部评论 (0)
还没有任何评论哟~