Codeforces1092C. Prefixes and Suffixes——————思维，字符串

àì夳堔傛蜴生んèń 2022-04-03 09:54 201阅读 0赞

# C. Prefixes and Suffixes #

Ivan wants to play a game with you. He picked some string s of length n consisting only of lowercase Latin letters.

You don’t know this string. Ivan has informed you about all its improper prefixes and suffixes (i.e. prefixes and suffixes of lengths from 1 to n−1), but he didn’t tell you which strings are prefixes and which are suffixes.

Ivan wants you to guess which of the given 2n−2 strings are prefixes of the given string and which are suffixes. It may be impossible to guess the string Ivan picked (since multiple strings may give the same set of suffixes and prefixes), but Ivan will accept your answer if there is at least one string that is consistent with it. Let the game begin!

## Input ##

The first line of the input contains one integer number n (2≤n≤100) — the length of the guessed string s.

The next 2n−2 lines are contain prefixes and suffixes, one per line. Each of them is the string of length from 1 to n−1 consisting only of lowercase Latin letters. They can be given in arbitrary order.

It is guaranteed that there are exactly 2 strings of each length from 1 to n−1. It is also guaranteed that these strings are prefixes and suffixes of some existing string of length n.

## Output ##

Print one string of length 2n−2 — the string consisting only of characters ‘P’ and ‘S’. The number of characters ‘P’ should be equal to the number of characters ‘S’. The i-th character of this string should be ‘P’ if the i-th of the input strings is the prefix and ‘S’ otherwise.

If there are several possible answers, you can print any.

## Examples ##

#### input ####

5  
ba  
a  
abab  
a  
aba  
baba  
ab  
aba

#### output ####

SPPSPSPS

#### input ####

3  
a  
aa  
aa  
a

#### output ####

PPSS

#### input ####

2  
a  
c

#### output ####

## Note ##

The only string which Ivan can guess in the first example is “ababa”.

The only string which Ivan can guess in the second example is “aaa”. Answers “SPSP”, “SSPP” and “PSPS” are also acceptable.

In the third example Ivan can guess the string “ac” or the string “ca”. The answer “SP” is also acceptable.

--------------------

题意：  
伊万想和你一起玩游戏。,他挑选了一些长度为n的字符串，仅由小写拉丁字母组成。 ,你不知道这个字符串。 伊万告诉了你所有的前缀和后缀（即前缀和后缀长度从1到n-1），但他没有告诉你哪些字符串是前缀，哪些是后缀。  
伊万希望你猜测给定的2n-2个字符串中哪一个是给定字符串的前缀，哪些是后缀。你可能无法猜出伊万选择的字符串（因为多个字符串可能会给出相同的后缀和前缀集），但如果至少有一个字符串与它一致，伊万将接受您的答案。,让游戏开始吧！  
输入  
输入的第一行包含一个整数n（2≤n≤100） - 字符串s的长度。  
接下来的2n-2行，包含前缀和后缀，每行一个。,它们中的每一个都是长度从1到n-1的字符串，仅由小写拉丁字母组成。,它们可以任意顺序给出。  
保证每个长度恰好有2个字符串，从1到n-1。,还保证这些字符串是一些长度为n的现有字符串的前缀和后缀。  
输出  
打印一串长度为2n-2的字符串 - 仅由字符“P”和“S”组成的字符串。,字符“P”的数量应该等于字符“S”的数量。,如果输入字符串的第i个是前缀，则该字符串的第i个字符应为“P”，否则为“S”。 ,如果有多个可能的答案，您可以打印任何答案。

--------------------

思路：  
把所有字符串记录下位置，然后按照长度排序；  
将长度为1和n-1的字符串连起来，这样就构成了一个长度为n的字符串，一共有4中情况。  
然后和给定的2n-2个前缀后缀比较，如果能够全部匹配，那就说明构造的这个长度为n的字符串(可能)是原串，比较的过程中记录一下那些是前缀，那些是后缀。最后输出就好

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 307;
    struct node{
        
            string s;
            int id;
    }a[MAXN];
    char ans[MAXN];
    int n;
    bool cmp(node x,node y)
    {
        
            return x.s.size()<y.s.size();
    }
    
    bool isPre(string s,string t)//是前缀
    {
        
            for(int i=0;i<t.size();++i)
                    if(s[i]!=t[i])
                            return false;
            return true;
    }
    bool isSuf(string s,string t)//是后缀
    {
        
            for(int i=t.size()-1;i>=0;--i)
                    if(s[s.size()-t.size()+i]!=t[i])
                            return false;
            return true;
    }
    
    void slove(string S)
    {
        
            for(int i=1;i<=n;i+=2)
            {
        
                    if(isPre(S,a[i].s) && isSuf(S,a[i+1].s))//两个长度相同的子串必定有一个是前缀，一个后缀
                    {
        
                            ans[a[i].id]='P';
                            ans[a[i+1].id]='S';
                            continue;
                    }
                    if(isPre(S,a[i+1].s) && isSuf(S,a[i].s))
                    {
        
                            ans[a[i].id]='S';
                            ans[a[i+1].id]='P';
                            continue;
                    }
                    return ;
            }
            for(int i=1;i<=n;++i)
                    cout<<ans[i];
            cout<<endl;
            exit(0);
    }
    int main()
    {
        
    
            cin>>n;
            n = n*2 - 2;
            for(int i=1;i<=n;++i)
            {
        
                    cin>>a[i].s;
                    a[i].id = i;
            }
            sort(a+1,a+n+1,cmp);
            if(n==2)
            {
        
                    puts("PS");
                    return 0;
            }
            slove(a[1].s+a[n-1].s);
            slove(a[1].s+a[n].s);
            slove(a[2].s+a[n-1].s);
            slove(a[2].s+a[n].s);
            return 0;
    }