HDU3068 最长回文马拉车 Manacher

朴灿烈づ我的快乐病毒、 2022-05-11 14:28 220阅读 0赞

Problem Description  
给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.  
回文就是正反读都是一样的字符串,如aba, abba等  
Input  
输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S  
两组case之间由空行隔开(该空行不用处理)  
字符串长度len <= 110000  
Output  
每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.  
Sample Input  
aaaa  
abab  
Sample Output  
4  
3

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #define Max 110005
    using namespace std;
    char Ma[Max*2];
    int Mp[Max*2];
    void Manacher(char s[],int len)
    {
    	int l=0,i,j;
    	Ma[l++]='$';
    	Ma[l++]='#';
    	for(i=0;i<len;i++)
    	{
    		Ma[l++]=s[i];
    		Ma[l++]='#';
    	}
    	Ma[l]=0;
    	int mx=0,id=0;
    	for(i=0;i<l;i++)
    	{
    		Mp[i]=mx>i?min(Mp[2*id-i],mx-i):1;
    		while(Ma[i+Mp[i]]==Ma[i-Mp[i]])
    			Mp[i]++;
    		if (i+Mp[i]>mx)
    		{
    			mx=i+Mp[i];
    			id=i;
    		}
    	}
    }
    int main()
    {	
    	char s[Max];
    	int len,ans,i;
    	while(scanf("%s",s)!=EOF)
    	{
    		len=strlen(s),ans=0;
    		Manacher(s,len);
    		for(i=0;i<2*len+2;i++)
    		ans=max(ans,Mp[i]-1);
    		printf("%d\n",ans);
    	}
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关最长回文子串（马拉车算法）

长回文子串，即正反读起来都一样，例如“ababa”。Manacher Algorithm算法利用了回文的重复特性，让时间复杂度降为了O(n)。马拉车算法详解： 1...

男娘i/ 2024年04月17日 06:28/ 0 赞/ 88 阅读

相关 Manacher's algorithms（马拉车算法）最长回文子串

最长回文子串 > https://leetcode-cn.com/problems/longest-palindromic-substring/ 给定一个字符串 s，找

太过爱你忘了你带给我的痛/ 2023年05月31日 04:58/ 0 赞/ 30 阅读

相关马拉车算法（manacher）求最长回文子串

关于回文字符串的概念大家可以大致去搜索一下，这里不赘述。一、解题思路当前字符串 ![20200605082139621.png][] 最长回文子串： ![20

冷不防/ 2023年02月15日 10:18/ 0 赞/ 128 阅读

相关 HDU - 3068 最长回文(manacher模板题)

[点我看题][Link 1] 题意：求给定的一串字符串中最长的回文子串。分析：manacher(马拉车模板题。推荐学习博客：[https://www.cnblo

╰半夏微凉°/ 2022年06月04日 02:30/ 0 赞/ 202 阅读

相关 HDU3068 最长回文马拉车 Manacher

Problem Description 给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度. 回文就是正反读都是一样的字符串,如aba

朴灿烈づ我的快乐病毒、/ 2022年05月11日 14:28/ 0 赞/ 221 阅读

相关 51Nod 1088 最长回文子串——————Manacher,马拉车算法

-------------------- [ 51Nod 1088 最长回文子串][51Nod 1088] 基准时间限制：1 秒空间限制：131072 KB

深藏阁楼爱情的钟/ 2022年05月10日 14:36/ 0 赞/ 230 阅读

相关【3068 HDU】最长回文串（Manacher算法）

题目：[点击打开题目链接][Link 1] 思路：这题要用到回文串匹配的知识点。我们之前遇到这种题传统思想就是分奇数和偶数情况进行暴力，从前往后遍历每一个字符，然后以该字符为

忘是亡心i/ 2022年05月10日 13:26/ 0 赞/ 278 阅读

相关 HDU 3068 最长回文——————Manacher

最长回文 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

蔚落/ 2022年05月09日 12:20/ 0 赞/ 232 阅读

相关 (manacher 1.1)hdu 3068回文(使用manacher判断回文简单题)

最长回文 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

小鱼儿/ 2022年03月01日 06:06/ 0 赞/ 212 阅读

相关 HDU - 3068 最长回文【马拉车】题解

目录 1.题目 2.代码 1.题目给出一个只由小写英文字符a,b,c…y,z组成的字符串S,求S中最长回文

冷不防/ 2021年07月24日 23:06/ 0 赞/ 357 阅读