P3805 manacher算法最长回文子串长度 【马拉车算法】【模板】

P3805 manacher算法

题目地址:https://www.luogu.com.cn/problem/P3805

思路

马拉车其实就是每次算某个点的回文半径到时候,会看自身是否处在一个之前求过的回文串T中,然后根据镜面对称,O(1)获取以自己为中心在T中的最大回文子串,然后再尝试暴力,所有的更新暴力复杂度为O(n)

代码

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e7+2e6 + 10;//没错这题有512MB内存,这里最多会用到300MB
using namespace std;

string s;
int ans[maxn],str[maxn],lef[maxn];
int build(const string &s){
    int n = s.length(), m = (n + 1)*2, ret = 0;
    str[0] = '$'; str[m] = '@'; str[1] = '#'; ans[1] = 1;
    for (int i = 1; i <= n; i++) 
        str[i*2] = s[i - 1], str[i*2+1] = '#';
    ans[1] = 1;
    for (int r = 0, p = 0, i = 2; i < m; ++i){
        if (r > i) ans[i] = min(r - i, ans[p * 2 - i]); 
        else ans[i] = 1; 
        while(str[i - ans[i]] == str[i + ans[i]]) ++ans[i];
        if (i + ans[i] > r) r = i + ans[i], p = i;
        ret = max(ret, ans[i] - 1);
    }
    return ret;
}

int main(){
    ios;
    cin>>s;
    int res = build(s);
    cout<<res<<endl;
    return 0;
}
Ryuichi的算法分享 文章被收录于专栏

分享我的一些算法题解,致力于把题解做好,部分题解可能会采用视频的形式来讲解。

全部评论

相关推荐

05-12 11:09
已编辑
门头沟学院 后端
已注销:没必要放这么多专业技能的描述。这些应该是默认已会的,写这么多行感觉在凑内容。项目这块感觉再包装包装吧,换个名字,虽然大家的项目基本都是网上套壳的,但是你这也太明显了。放一个业务项目,再放一个技术项目。技术项目,例如中间件的一些扩展和尝试。
简历中的项目经历要怎么写
点赞 评论 收藏
分享
程序员小白条:你是沟通了900个,不是投了900份简历,你能投900份,意味着对面都要回复你900次,你早就找到实习了,没亮点就是这样的,别局限地区,时间投的也要早,现在都要7月了
点赞 评论 收藏
分享
八股刚起步,看了javaguide,小林coding,还有面渣,感觉面渣是体验最好的,请问只看面渣够用吗,有不完善的需要补吗?
码农索隆:先背最基础的知识,然后理解情景题,现在面试大多数喜欢问情景题,更考验面试者的基础和临场发挥情况
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务