题目大意
给你一个初始字符串s，你可以删除字符串s中的某个字符(比如删除'a'就是把s中的所有'a'删掉)得到一个字符串t，把t拼接到s后面，再在t中删除其他字符，继续拼接到s后面直到t为空，给你最后拼接出的数字，让你还原原来的数字并输出字符的删除顺序。
解题思路
感觉输出字符的删除顺序算是个小提示？我的思路就是从删除顺序入手的。首先因为字符是一个一个删除的，所以倒着遍历一遍拼接出来的字符串，每个字符第一次出现的顺序正好是删除顺序的倒序。
然后我们可以发现，假如字符的删除序列长度为3，比如说"abacabaaacaac"这个样例，删除序列为"bac"，那么把原字符串中每个字符的出现次数即为(cnt[ch_i])，那么字符'c'就出现了(cnt[c] imes 3)次，字符'a'就出现了(cnt[a] imes 2)次，字符'b'就出现了"cnt[b] imes 1"次。
观察样例还能发现一个性质：将每个t分成一段，后一段一定是前一段的子序列。
我们倒着来遍历拼接出来的字符串，根据第一个性质，我们可以计算出每一组t包含的字符数量，于是我们能得到每组t位于哪个区间，然后我们还能得出在这组t中，每个字符应该出现的次数为多少，这个是判断方案合法的根据之一，当然，只有数够是不一定合法的，还得根据第二个性质，判断前一个区间是否是当前区间的子序列。
const int maxn = 2e5+10;
const int maxm = 2e7+10;
int cnt[30], cnt2[maxn];
string s;
bool judge(int l1, int r1, int l2, int r2) {
int cnt = 0, len = r2-l2+1;
for (int i = l1; i<=r1; ++i) {
if (l2<=r2 && s[l2]==s[i]) ++l2, ++cnt;
}
return cnt == len;
}
int main() {
IOS;
int __; cin >> __;
while(__--) {
clr(cnt, 0);
cin >> s;
string od;
for (int i = s.size()-1; i>=0; --i) {
if (!cnt[s[i]-'a']) od += s[i];
++cnt[s[i]-'a'];
}
reverse(od.begin(), od.end());
int p = od.size()-1, t = od.size();
if (t==1) {
cout << s << ' ' << od << endl;
continue;
}
string ans; vector<P> tmp;
bool ok = 1;
if (cnt[od[p]-'a']%t) ok = 0;
int sum = cnt[od[p]-'a']/t, res = sum, r = s.size()-1;
for (int i = s.size()-1; i>=0 && ok; --i) {
--res; ++cnt2[s[i]-'a'];
if (res==0) {
for (int i = p; i<od.size(); ++i)
if (cnt2[od[i]-'a']!=cnt[od[i]-'a']/(i+1)) ok = 0;
clr(cnt2, 0);
tmp.push_back({i, r});
r = i-1;
if (ok && tmp.size()>1) {
auto it = tmp.rbegin();
int l1 = it->x, r1 = it->y;
++it;
int l2 = it->x, r2 = it->y;
if (!judge(l1, r1, l2, r2)) ok = 0;
}
--p, --t;
if (t && cnt[od[p]-'a']%t) ok = 0;
sum += cnt[od[p]-'a']/t;
res = sum;
if (p==0) {
if (sum!=i) ok = 0;
ans = s.substr(0, i);
break;
}
}
}
tmp.push_back({0, r});
if (ok && tmp.size()>1) {
auto it = tmp.rbegin();
int l1 = it->x, r1 = it->y;
++it;
int l2 = it->x, r2 = it->y;
if (!judge(l1, r1, l2, r2)) ok = 0;
}
if (ok) cout << ans << ' ' << od << endl;
else cout << -1 << endl;
}
return 0;
}