manacher算法

短命女 2021-12-19 03:55 251阅读 0赞

hdu：3068

\#include <stdio.h>  
\#include <iostream>  
\#include <string.h>  
\#include <algorithm>  
using namespace std;  
int min(int a,int b)  
\{  
return a<b?a:b;  
\}  
char s\[110006\];  
char t\[110006\*3\];  
int p\[110006\*3\]=\{0\};  
int n=1;  
void change(char r\[\])  
\{  
int len=strlen(r);  
int i;  
t\[0\]='$';  
for(i=0;i<len;i++)  
\{  
t\[n++\]='\#';  
t\[n++\]=s\[i\];  
\}  
t\[n\]='\#';  
cout<<t<<endl;  
\}  
void manacher()  
\{  
int id=0,mxright=0;  
for(int i=1;i<=n;i++)  
\{  
if(mxright>i)  
\{  
p\[i\]=min(p\[2\*id-i\],mxright-i);  
\}  
else  
\{  
p\[i\]=1;  
\}  
while(t\[i+p\[i\]\]==t\[i-p\[i\]\])  
\{  
p\[i\]++;  
\}  
if(p\[i\]+i>mxright)  
\{  
mxright=p\[i\]+i;  
id=i;  
\}  
\}  
\}  
int main()  
\{  
while(scanf("%s",s)!=EOF)  
\{  
change(s);  
manacher();  
int mx=0;  
for(int i=1;i<=n;i++)  
\{  
if(mx<p\[i\])  
\{  
mx=p\[i\];  
\}  
\}  
cout<<mx-1<<endl;  
memset(p,0,sizeof(p));  
memset(s,'\\0',sizeof(s));  
memset(t,'\\0',sizeof(t));  
n=1;  
\}  
return 0;  
\}

不懂可以参考大佬讲解：http://www.61mon.com/index.php/archives/181/

转载于:https://www.cnblogs.com/chinacwj/p/7083141.html

发表评论取消回复

表情：

评论列表（有 0 条评论，251人围观）

还没有评论，来说两句吧...

相关阅读

相关 Manache算法

今天看到这个单词就很奇怪！！撸一撸… Manacher算法的详细讲解 Manacher算法，又叫“马拉车”算法，可以在时间复杂度为O(n)的情况下求解一个字符串的最长回

待我称王封你为后i/ 2023年07月17日 02:46/ 0 赞/ 3 阅读

相关 Manacher 算法

0. 问题定义最长回文子串问题：给定一个字符串，求它的最长回文子串长度。如果一个字符串正着读和反着读是一样的，那它就是回文串。下面是一些回文串的实例：

待我称王封你为后i/ 2022年06月01日 03:30/ 0 赞/ 196 阅读

相关 manacher算法（回文字符串）

定义数组p\[i\]表示以i为中心的(包含i这个字符)回文串半径长将字符串s从前扫到后for(int i=0;i<strlen(s);++i)来计算p\[i\],则最大的p

柔情只为你懂/ 2022年05月24日 02:17/ 0 赞/ 199 阅读

相关 Manacher算法

一、[概要][Link 1] ![这里写图片描述][70] 二、算法实现 / 最大需要回文串的长度 @author superman / p

短命女/ 2022年05月15日 09:55/ 0 赞/ 184 阅读

相关【算法】——Manacher Algorithm（马拉车算法）

一、马拉车算法来源马拉车算法Manacher‘s Algorithm是用来查找一个字符串的[最长回文子串][Link 1]的线性方法，由一个叫Manac

- 日理万妓/ 2022年05月14日 04:43/ 0 赞/ 237 阅读

相关 Manacher算法

原文：https://blog.csdn.net/dyx404514/article/details/42061017 Manacher算法算法总结第三弹 man

今天药忘吃喽~/ 2022年04月17日 03:35/ 0 赞/ 190 阅读

相关 manacher算法

hdu：3068 \include <stdio.h> \include <iostream> \include <string.h> \include <alg

短命女/ 2021年12月19日 03:55/ 0 赞/ 252 阅读

相关【搞定算法】Manacher 马拉车算法

求一个字符串中的最长回文子串，这是一道经典的面试题目，解法有很多，详细可见：最长回文子串问题。其实个人感觉 Manacher 算法代码实现还是有一定难度的，真正在做题目的时候采

朴灿烈づ我的快乐病毒、/ 2021年12月17日 00:33/ 0 赞/ 307 阅读

相关数据结构与算法之Manacher算法

数据结构与算法之Manacher算法 -------------------- 目录 1. Manacher算法概述 2. Manacher算法代码实现 3.

素颜马尾好姑娘i/ 2021年12月16日 13:53/ 0 赞/ 321 阅读

相关 manacher算法

manacher算法是在O(n)的复杂度内求回文串长度的算法。算法过程如下。先在所有字符之间加上一种没有意义的字符。比如“\”，“|”等。来去除偶数回文和奇数回文的

末蓝、/ 2021年12月09日 18:53/ 0 赞/ 269 阅读