问题 G: 还原字符串
传统题
1.000s
时间限制
256MB
内存限制
1 提交
1 解决
【题目描述】
题目描述
有一个小写英文字符串 s
，将这个字符串复制一份，再与原字符串拼接，将会得到 s⋅s
，接下来，将这个双倍字符串的某个位置插入某个小写英文字母，最后得到一个字符串 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