小A的回文串

佚名 6年前 (2019-04-13) 随笔 360人围观抢沙发百度已收录

题面：https://ac.nowcoder.com/acm/contest/549/B

寻找一个字符串中的最长回文子串；

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

找回文子串可以从两端开始，但也可以从中间扩展出去；

可以将环形的字符串展开成直线型；

#include<iostream>
#include<cstring>
using namespace std;
const int maxn=5e3+10;
char s[2*maxn];
int len,ans;
int check(int l,int r);
int main()
{
    ans=-1;
    cin>>s;
    len=strlen(s);
    for(int i=0; i<len; i++)
        s[len+i]=s[i];
    for(int i=0; i<2*len; i++)
    {
        int cnt,l,r;
        cnt=1,l=i-1,r=i+1;
        while(check(l,r))
        {
            if(s[l]==s[r])
            {
                cnt+=2;
                l--;
                r++;
            }
            else
                break;
        }
        ans=max(ans,cnt);
        cnt=0,l=i,r=i+1;
        while(check(l,r))
        {
            if(s[l]==s[r])
            {
                cnt+=2;
                l--;
                r++;
            }
            else
                break;
        }
        ans=max(ans,cnt);
    }
    cout<<ans<<endl;
    return 0;
}
int check(int l,int r)
{
    if(l>=0&&r<2*len&&r-l+1<=len)
        return 1;
    return 0;
}