样例

Input

5
ba
a
abab
a
aba
baba
ab
aba

Output

SPPSPSPS

Input

3
a
aa
aa
a

Output

PPSS

题意：

就是给目标字符串的所有前缀和后缀  但是不告诉你哪个是前缀那个是后缀

让你去判断     前缀就输出  P   后缀输出S    结果不唯一  符合题意就ok

解法：

因为给出了目标串的所有前缀和后缀  那么  我们找到最长的那两个

这两个肯定一个是前缀 一个是后缀

然后我们拿到最长的前缀串  去遍历所有给出的字符串  是前缀的肯定前边部分相同  不相同的就输出S

但是如何判断最长的两个谁是前缀谁是后缀呢？方法如下：

比如   目标串是  “abcde”   那么 前缀串和后缀串中最长的两个  是 abcd 和 bcde

如果 abcd 去掉第一个字母 等于  bcde去掉最后一个字母   那么abcd就是前缀

反之  abcd就是后缀

写到这里 看似解决了所有的问题了  但是还有一个特殊情况 回文串

比如 目标串是     ababa   这种情况

5
ba
a
baba
a
aba
abab
ab
aba

最长的两个是  baba 和 abab   这两个无法判断出来谁是前缀谁是后缀

所以 我们还需要加个操作 解决这种特殊情况

我们在两个最长的串中 随便选一个 当作前缀   去遍历所给的所有串

如果 其他串等于这个串的前面部分 那么就符合前缀  计数 看看有几个符合前缀的

如果符合前缀的串的数量大于等于一半  那么他就是前缀  否则他是后缀

ps：还需要注意一个小问题 有的串既符合前缀又符合后缀  但是输出P和S的数量要相等，我们需要一个标记，来保证输出的P和S的数量一样。

代码

#include<bits/stdc++.h>
using namespace std;
int cnt[300],n,f;
int main(){
    string mx1="",mx2="",pr,s[300];
    scanf("%d",&n);getchar();
    for(int i=1;i<=2*n-2;i++){
        cin>>s[i];
        if(s[i].size()==n-1){//记录最长的
            if(mx1.size()==0)mx1=s[i];
            else mx2=s[i];
        }
    }
    for(int i=1;i<=2*n-2;i++){//计数
        if(mx1.substr(0,s[i].size())==s[i])f++;
    }
    //判断前缀后缀
    if(f>=(2*n-2)/2 && mx1.substr(1,n-2)==mx2.substr(0,n-2)){
        pr=mx1;
    }
    else{
        pr=mx2;
    }
    
    for(int i=1;i<=n*2-2;i++){
        if(s[i]==pr.substr(0,s[i].size()) && cnt[s[i].size()]!=1){
            cnt[s[i].size()]=1;//做标记
            printf("P");
        }
        else{
            printf("S");
        }
    }
}