codeforces-GlobleRound7-D2

codeforces-GlobleRound7-D2

七月 08, 2020

D2. Prefix-Suffix Palindrome (Hard version)

题意
要求从s中找到一个t
使得 t的长度不超过s
t是回文串
存在s的前缀a和后缀b a+b=t
|s|<1e5

题解
先从两边取对称的前后缀，之后再取余下字符串较长的回文前缀或后缀用马拉车实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# include<bits/stdc++.h>

# define endl "\n"

using namespace std;
typedef long long ll;
///字符串预处理,插入#,则实际回文串长度等于插入后半径p[i]-1
inline string makestr(string str){
    string t="#";///在开头和结尾多插入'$'防止越界
    for(int i=0;i<str.size();i++)t+=str[i],t+='#';
    return t;
}
string malacher(string str){
    string t=makestr(str);
    //cout<<t<<endl;
    vector<int>p(t.size(),0);
    int mx=0,id=0,ilenth=0,icenter=0;
    ///mx 表示当前右侧最远的回文子串右端位置 id 表示当前右侧最远的回文子串中间字符位置
    ///ilenth表示最长回文子串长度,icenter表示最长回文子串中间位置
    for(int i=1;i<t.size();i++){
        ///利用mx和id,和回文串对称性质动态更新以任意一个字符为中心的回文串半径
        p[i]=i<mx?min(p[2*id-i],mx-i):1;///p [2*id-i]=p[j] (j是i关于id对称点 因为id-j=i-id所以j=id-(i-id)=2*id-i )
        while(t[i-p[i]]==t[i+p[i]])p[i]++;
        if(p[i]+i>mx){
            mx=p[i]+i;
            id=i;
        }
        if(p[i]>ilenth){
            ilenth=p[i];
            icenter=i;
        }
    }
    int Maxlen=0;///p[i]==i+1 以第i位为中心的回文串长度=p[i],若它是前缀则长度也=i+1(0也计入)
    for(int i=0;i<t.size();i++)if(p[i]==i+1)Maxlen=p[i];///此步适应了本题做的改动
    return str.substr(0,Maxlen-1);///插入#,则实际回文串长度等于插入后半径p[i]-1
    ///首位置,预处理后的长度-1
}
int main(){
    int t;cin>>t;
    while(t--){
        string s;cin>>s;
        int l=0,r=s.size()-1;
        while(s[l]==s[r]&&l<r)l++,r--;
        string s1=s.substr(l,r-l+1);
        string s2=s1;reverse(s1.begin(),s1.end());
        //cout<<s1<<" "<<s2<<endl;
        s1=malacher(s1);
        s2=malacher(s2);
        //cout<<s1<<" "<<s2<<endl;
        cout<<s.substr(0,l)<<(s1.size()>s2.size()?s1:s2)<<s.substr(r+1)<<endl;
    }
}