+1学姐在线嘤嘤嘤

Description

 

众所周知，+1学姐人美心好又聪明，但就是没有男朋友，你说气不气。这也正常，成为她的男朋友必须要答对她的问题才行，你想接受挑战吗？今天，+1学姐给出的问题是：有一个长度为n的字符串，告诉你该字符串的n-1个前缀子字符串，和n-1个后缀子字符串，为了增加难度，+1学姐给出的顺序是乱的，她要让你回答这2*n-2 个字符串是前缀的还是后缀的，若该字符串为前缀的，回答‘P’，若为后缀的，回答‘S’。你想成为+1学姐的男朋友吗？那就A了这道题吧。例如：字符串abcd，前缀子字符串为:a, ab, abc 后缀子字符串为:d, cd, bcd.

Input

 

输入的第一行包含一个整数n（2<=n<=100）,原始字符串的长度。

接下来的2n-2行，每行有一个字符串，是原始字符串的前缀或后缀。

给出的每一个字符串的的长度都为1到n-1，保证每个长度的字符串有两个，且由小写字母组成，给出的顺序是任意的。

Output

 

输出一个长度为2n-2，且仅由字符‘P’和‘S’组成的字符串。按顺序输出，若给出的第k个字符串为前缀的，那么输出的字符串第k个应为'P'.答案保证唯一。

Sample Input 1 

4
cd
abc
a
bcd
d
ab

Sample Output 1

SPPSSP

Hint

样例中原始字符串为:abcd.前缀的：a, ab, abc后缀的：d, cd, bcd所以输出：SPPSSP

思路：先把首尾两个字母找出来，如何还原串，在find子串

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm> 
using namespace std;
string s[205];
int P[40],S[40],l[205];
queue<char> q1,q2;
bool vis[30];
int main() {
	int n;
	scanf("%d",&n);
	for(int i=1; i<=2*n-2; i++) {
		cin>>s[i];
		l[i]=s[i].size();
		P[s[i][0]-'a']++;
		S[s[i][l[i]-1]-'a']++;
	}
	for(int i=0; i<26; i++) {
		if(P[i]>=n-1) q1.push('a'+i);
		if(S[i]>=n-1) q2.push('a'+i);
	}
	char a,b;
	if(q1.size()==1&&q2.size()>1) {
		a=q1.front();
		vis[a-'a']=true;
		while(!q2.empty()){
			char t=q2.front();
			q2.pop();
			if(!vis[t-'a']){
				b=t;
				break;
			}
		}
	}
	else if(q2.size()==1&&q1.size()>1) {
		b=q2.front();
		vis[b-'a']=true;
		while(!q1.empty()){
			char t=q1.front();
			q1.pop();
			if(!vis[t-'a']){
				a=t;
				break;
			}
		}
	}
	else{
		a=q1.front();
		b=q2.front();
	}
	string sss;
	for(int i=1;i<=2*n-2;i++){
		if(l[i]==n-1&&s[i][0]==a){
			sss=s[i]+b;
			break;
		}
	}
	for(int i=1;i<=2*n-2;i++){
		if(sss.find(s[i])==0)
		printf("P");
		else
		printf("S");
	}
    return 0;
}