CF1092C.Prefixes and Suffixes (字符串） 1700

题意

题目链接：Problem - C - Codeforces
题意：给你一个$n(n\leq 100)$，以及$2n-2$个字符串，包括了不含本身的所有前缀和后缀，例如carry则有：

c
ca
car
carr
y
ry
rry
arry

请按照原来顺序输出字符串是前缀('P')还是后缀('S')，如果有多种符合的，输出任意一种，但是如果相同长度，哪怕都相等，例如都为'a'和'a'，也只能存在一个前缀一个后缀。

思路

这个题wa麻了，主要难点在于
- 相同长度二者必须不同，一个为P一个为S。
- 如何求出这个长度为$n$的字符串

整体思想就是对于所有字符串进行排序，这样长度变成了1,1,2,2,3,3,...

sort(ss+1,ss+1+m,[](const node& a,const node& b){return a.s.size()<b.s.size();});

每次处理就处理1,3,5,...，这样处理完当前字符串，那么+1的类型就是相反的，好比s[i]应该输出'P'，那么我设置s[i+1]就应该输出'S'。

    for (int i=1;i<=m;i+=2)
    {
        int l = ss[i].s.size();
        bool okP = true;
        for (int j=0;j<l;j++)
            if (st[j]!=ss[i].s[j])
                okP = false;//不满足P
        if (okP) ans[ss[i].id] = 1,ans[ss[i+1].id] = 2;
        else ans[ss[i+1].id] = 1,ans[ss[i].id] =2;//成对处理
    }

那么这个字符串st是如何得来的呢？
——可以得出，令最长的两个字符串为s1,s2,那么答案只可能是s1+s2.back()或者s2+s1.back()，例如carry中得出最长的就是carr和arry，那么字符串只可能在carr+y=carry里面，或者是arry+c=arryc，然后二者拿一个出去判断真假就行。

    string s1,s2,st;
    s1 = ss[m].s + ss[m-1].s.back();
    s2 = ss[m-1].s + ss[m].s.back();
    bool ok1 = true, ok2 = true,okP,okS;
    for (int i=1;i<=m;i++)
    {
        string res = ss[i].s;
        okP = okS = true;
        int l = ss[i].s.size();
        for (int j=0;j<l;j++)
            if (s1[j]!=ss[i].s[j])
                okP = false;
        for (int j=0;j<l;j++)
            if (s1[n-1-j]!=ss[i].s[l-1-j])//逐个比较
                okS = false;
        if (!okP&&!okS) break;//都不满足前后缀
    }
    if (!okP&&!okS) st = s2;//s1不满足，那么就是s2是正确的
    else st = s1;//相反情况

最后只需要输出即可。

代码

map<char,int> mp;

struct node
{
    string s;
    int id;
}ss[N];
inline void Case_Test()
{
    cin>>n;
    m = 2*n-2;
    for (int i=1;i<=m;i++)
    {
        cin>>ss[i].s;
        mp[ss[i].s.front()]++;
        mp[ss[i].s.back()]++;
        str[i] = ss[i].s;
        ss[i].id = i;
    }
    sort(ss+1,ss+1+m,[](const node& a,const node& b){return a.s.size()<b.s.size();});
    string s1,s2,st;
    s1 = ss[m].s + ss[m-1].s.back();
    s2 = ss[m-1].s + ss[m].s.back();
    bool ok1 = true, ok2 = true,okP,okS;
    for (int i=1;i<=m;i++)
    {
        string res = ss[i].s;
        okP = okS = true;
        int l = ss[i].s.size();
        for (int j=0;j<l;j++)
            if (s1[j]!=ss[i].s[j])
                okP = false;
        for (int j=0;j<l;j++)
            if (s1[n-1-j]!=ss[i].s[l-1-j])
                okS = false;
        if (!okP&&!okS) break;
    }
    if (!okP&&!okS) st = s2;
    else st = s1;
    vector<int> num(4,0);
    for (int i=1;i<=m;i+=2)
    {
        int l = ss[i].s.size();
        bool okP = true;
        for (int j=0;j<l;j++)
            if (st[j]!=ss[i].s[j])
                okP = false;
        if (okP) ans[ss[i].id] = 1,ans[ss[i+1].id] = 2;
        else ans[ss[i+1].id] = 1,ans[ss[i].id] =2;
    }
    for (int i=1;i<=m;i++) 
        if (ans[i]==1) cout<<"P";
        else cout<<"S";
}