题目：Prefixes and Suffixes
思路：
可以知道原序列一定是由给出的最长的两个字符串拼接而成的，所以可以尝试把最长的两个字符串按两种相对位置拼接。
设一个数组b。
对于每种拼接方法——
如果一个串可以放在前缀的位置而不能放在后缀的位置，就把b[i]设为1。
如果一个串可以放在后缀的位置而不能放在前缀的位置，就把b[i]设为2。
如果一个串可以放在前缀的位置也可以放在后缀的位置，就把b[i]设为0。
如果都不能放，就说明这种情况不可行。
然后对于两个b为0的相同子串，用一个map存储，分别放在前缀和后缀就好了。
代码：
#include<bits/stdc++.h>
using namespace std;#define read(x) scanf("%d",&x)
#define maxn 10000int n;
string s[maxn*2+5];string s1,s2,s3,s4;
string a;
int b[maxn+5];map<string,int> mp;int main() {
read(n);for(int i=1; i<=n*2-2; i++) {
cin>>s[i];if(s[i].size()==n-1) {
if(s1.size()==0) s1=s[i];else s2=s[i];}if(s[i].size()==1) {
if(s3.size()==0) s3=s[i];else s4=s[i];}}if(s1+s2[s2.size()-1]==s1[0]+s2&&((s3[0]==s1[0]&&s4[0]==s2[s2.size()-1])||(s4[0]==s1[0]&&s3[0]==s2[s2.size()-1]))) {
a=s1+s2[s2.size()-1];} else a=s2+s1[s1.size()-1];int ans1=0,ans2=0;FRT:;for(int i=1;i<=n*2-2;i++) {
int f1=1,f2=1;for(int j=0;j<s[i].size();j++) {
if(s[i][j]!=a[j]) {
f1=false;break;}}for(int j=0;j<s[i].size();j++) {
if(s[i][j]!=a[n-s[i].size()+j]) {
f2=false;break;}}if(f1&&!f2) b[i]=1,ans1++;else if(f2&&!f1) b[i]=2,ans2++;else if(0==f1&&0==f2) {
for(int x=1;x<a.size();x++)swap(a[x-1],a[x]);ans1=0,ans2=0;memset(b,0,sizeof(b));goto FRT;}}for(int i=1;i<=n*2-2;i++) {
if(b[i]==1) {
printf("P");} else if(b[i]==2) {
printf("S");} else if(mp.count(s[i])) {
int y=3-mp[s[i]];if(y==1) {
printf("P");ans1++;} else {
printf("S");ans2++;}} else {
if(ans1<n-1) {
printf("P");ans1++;mp[s[i]]=1;} else {
printf("S");ans2++;mp[s[i]]=2;}}}return 0;
}