一道字符串题。
我们考虑还原字符串后再一个一个的判断。很显然，这个字符串是由一个长度为 \(n-1\) 的前缀和后缀组成的。因此我们可以找到这 \(2\) 个长度为 \(n\) 的字符串，然后枚举哪个是前缀，哪个是后缀。
值得注意的是，当你判断一个字符串为前缀时，如果后面出现了同样的字符串，你只能判断它为后缀。
Code
#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
int n;
bool flag;
string s1, s2, t, ans1, ans2; // t 是还原串
string s[205];
map <string, bool> mp;
bool check1(string str) { // 判断这个字符串是否是还原串的前缀
for (int i = 0; i < str.size(); i++) {
if (t[i] != str[i]) return 0;
}
return 1;
}
bool check2(string str) { // 判断这个字符串是否是还原串的后缀
int cnt = t.size() - 1;
for (int i = str.size() - 1; i >= 0; i--) {
if (t[cnt--] != str[i]) return 0;
}
return 1;
}
signed main() {
ios :: sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= 2 * n - 2; i++) cin >> s[i];
for (int i = 1; i <= 2 * n - 2; i++) {
if (s[i].size() == n - 1 and flag) s2 = s[i];
if (s[i].size() == n - 1 and !flag) {
s1 = s[i];
flag = 1;
}
}
flag = 0;
t = s1;
t += s2[s2.size() - 1];
// 如果 s1 是前缀
for (int i = 1; i <= 2 * n - 2; i++) {
if (!check1(s[i]) and !check2(s[i])) flag = 1; // 当 s1 是前缀时不合法
else {
if (check1(s[i]) and mp.find(s[i]) == mp.end()) {
ans1 += 'P';
mp[s[i]] = 1;
}
else ans1 += 'S';
}
}
t = s2;
t += s1[s1.size() - 1];
// 如果 s1 是后缀
mp.clear();
for (int i = 1; i <= 2 * n - 2; i++) {
if (check1(s[i]) and mp.find(s[i]) == mp.end()) {
ans2 += 'P';
mp[s[i]] = 1;
}
else ans2 += 'S';
}
if (!flag) cout << ans1;
else cout << ans2;
return 0;
}