E. Polycarp and String Transformation（构造）
题目：E. Polycarp and String Transformation
题目链接：https://codeforces.com/contest/1560/problem/E
题意：有一个字符串s，对它进行操作，直到字符串为空。每次操作，可以把字符串s添加到字符串t的尾部，然后删除s的一种字符。给定字符串t，求字符串s和删除的字符的顺序。
例如s = “abacaba”；
删除‘b’;
t = “abacaba“；
s = “aacaa”；
删除‘a‘;
t = “abacabaaacaa“；
s = ‘c‘；
删除‘c‘
t = “abacabaaacaac“;
S = 空字符串；
输入：第一行输入测试用例个数t。
T行：每行输入字符串t。（t的长度 <= 5 * 10 ^ 5）
输出：如果存在字符串s可以通过操作得到t，则输出字符串s和删除的字符的顺序。否则输出-1。
问题分析：构造题。
解题思路：
显然，本题有且只有一个构造的方案。因为从后往前遍历字符串t，那么先遍历到的字符必然是后删除的。所以我们从后往前遍历字符串t就能够得到字符的删除顺序。有了字符串t和字符的删除顺序，我们就可以试着构造字符串s。
假设字符串删除顺序是’a’,’b’,’c’,那么必然有：
字符串s中’a’的个数 = 字符串t中‘a’的个数。这是因为字符‘a’从s添加到t的尾部只添加了一次，然后’a‘就被删除了。同理可以得到：
字符串s中’b’的个数 = 字符串t中’b’的个数的二分之一。
字符串s中’c’的个数 = 字符串t中’c’的个数的三分之一。
这样，有了字符串t和字符的删除顺序，我们就能够得到字符串s中各个字符的个数。显然，应该从t的头部取出字符串s，因为最开始时字符串s是一整个都添加给了t。
这样，我们就得到了字符串s和字符的删除顺序。但我们仍需要模拟一下s的删除操作，看看能不能得到字符串t，这是因为我们仅仅是通过字符的个数来确定的字符串s，却没有考虑各个字符间的先后顺序。若模拟后能得到字符串t，则输出s和字符的删除顺序，否则，输出-1。
AC代码：
#include<bits/stdc++.h>
using namespace std;
void solve(){
string s;
cin >> s;
map<char, int> p;
string ans2;
for(int i = s.size() - 1;i >= 0;i--){
if(p[s[i]] == 0) ans2.insert(0, 1, s[i]);
p[s[i]]++;
}
map<char, int> p2;
for(int i = 0;i < ans2.size();i++){
if(p[ans2[i]] % (i + 1) != 0){
cout << -1 << endl;
return;
}
p2[ans2[i]] = p[ans2[i]] / (i + 1);
}
string ans;
for(int i = 0;i < s.size();i++){
if(p2[s[i]] >= 1){
ans += s[i];
p2[s[i]]--;
}
else break;
}
for(int i = 0;i <= 25;i++){
if(p2[i + 'a'] != 0){
cout << -1 << endl;
return;
}
}
map<char, int> p3;
int j = 0, x = 0;
for(int i = 0;i < s.size();i++){
if(p3[ans[j]] == 0){
if(ans[j] != s[i]){
cout << -1 << endl;
return;
}
}
else i--;
j++;
if(j == ans.size()){
p3[ans2[x]] = 1;
x++;
j = 0;
}
}
cout << ans << " " << ans2 << endl;
}
int main(void){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}
时间复杂度：因为上面代码用了map容器，所以复杂度是O（nlogn），但可以优化到O（n）。
空间复杂度：O（n）。