Codeforces Global Round 7 D2.Prefix-Suffix Palindrome (Hard version) 马拉车算法

原题链接:https://codeforces.com/contest/1326/problem/D2

字符串问题,D1数据较小,暴力过了

题意大体是:给你一个字符串 s ,让你找一个字符串 t ,字符串 t = a + b ,a 和 b 分别是s 的前缀和后缀(a、b可以为空),使 t 为回文串,问 t 最长是多少,并打印出t

先介绍一下manacher算法(又称马拉车)

manacher是一个线性求最长回文子串的算法,时间复杂度O(n)

这里不做详细讲解了,只给出模板吧

首先要预处理

比如 s = "a b c b a"

处理后s = "@#a#b#c#b#a#"

void manacher(string s)
{
    int mx=0,p=0;
    for(int i=1;i<=len;i++)
    {
        if(mx>i)
            d[i]=min(mx-i,d[2*p-i]);//2*p-i为i关于p的对称点
        else
            d[i]=1;
        while(s[i-d[i]]==s[i+d[i]])
        {d[i]++;}
        if(d[i]+i>mx)
        {
            mx=d[i]+i;
            p=i;
        }
    }
}

原题先对字符串进行manacher预处理,然后从两端开始找相等字符,遇到第一个不相等的停下来,再根据manacher算出的d数组找出中间的字符,最后分别输出即可

原题代码:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int d[3000005],len;
void manacher(string s)
{
    int mx=0,p=0;
    for(int i=1;i<=len;i++)
    {
        if(mx>i)
            d[i]=min(mx-i,d[2*p-i]);
        else
            d[i]=1;
        while(s[i-d[i]]==s[i+d[i]])
        {d[i]++;}
        if(d[i]+i>mx)
        {
            mx=d[i]+i;
            p=i;
        }
    }
}
int main()
{
    int t;
    string c;
    cin>>t;
    while(t--)
    {
        cin>>c;
        len=0;
        int n=c.size();
        if(n==1){cout<<c<<endl;continue;}
        string s="";
        d[0]=0;
        s+="@";len++;
        for(int i=0;i<n;i++)
        {
            s+="#";len++;
            s+=c.substr(i,1);len++;
        }
        s+="#";
        for(int i=0;i<len+3;i++)
        {d[i]=0;}
        manacher(s);
        //////////////////////////////////////////
        int ii=0,jj=0;
        for(int i=1;i<=len;i++)
        {
            if(s[i]!=s[len-i+1])
            {ii=i;jj=len-i+1;break;}
        }
        if(ii==0&&jj==0){cout<<c<<endl;continue;}
        int zz=0,hh=0,z,h;
        for(int i=jj;i>=ii;i-=2)
        {
            int mid=(ii+i)/2;
            if((d[mid]+mid-1)>=i)
            {zz=i-ii+1;z=i;break;}
        }
        for(int i=ii;i<=jj;i+=2)
        {
            int mid=(i+jj)/2;
            if((mid-d[mid]+1)<=i)
            {hh=jj-i+1;h=i;break;}
        }
        if(zz>=hh)
        {
            for(int i=1;i<=z;i++)
            {if(s[i]!='#'){cout<<s[i];}}
            for(int i=jj+1;i<=len;i++)
            {if(s[i]!='#'){cout<<s[i];}}
            cout<<endl;
        }
        else
        {
            for(int i=1;i<ii;i++)
            {if(s[i]!='#'){cout<<s[i];}}
            for(int i=h;i<=len;i++)
            {if(s[i]!='#'){cout<<s[i];}}
            cout<<endl;
        }
    }
    return 0;
}

123

点赞
  1. suddenly说道:
    Safari iPhone iOS 11.3

    1

发表评论

电子邮件地址不会被公开。必填项已用 * 标注