hihoCoder#1032 : 最长回文子串(manacher算法)

╰+攻爆jí腚メ 2022-08-21 00:05 209阅读 0赞

参考http://blog.csdn.net/xingyeyongheng/article/details/9310555

#include<iostream>  
    #include<cstdio>  
    #include<cstdlib>  
    #include<cstring>  
    #include<string>  
    #include<queue>  
    #include<algorithm>  
    #include<map>  
    #include<iomanip>  
    using namespace std;
    const int MAX=1000010;
    int p[MAX*2] = {0};
    char s[MAX * 2];
    int main(){
    	int n;
    	cin >> n;
    	for (int j = 0; j < n;j++)
    	{
    		string word;
    		cin >> word;
    		int len = word.length(), id = 0, maxlen = 0;
    		for (int i = len; i >= 0; --i)  
    		{
    			s[i + i + 2] = word[i];
    			s[i + i + 1] = '#';
    		}
    		s[0] = '*';
    		for (int i = 2; i<2 * len + 1; ++i){
    			if (p[id] + id>i)p[i] = min(p[2 * id - i], p[id] + id - i);
    			else p[i] = 1;
    			while (s[i - p[i]] == s[i + p[i]])++p[i];
    			if (id + p[id] < i + p[i])id = i;
    			if (maxlen < p[i])maxlen = p[i];
    		}
    		cout << maxlen - 1 << endl;
    	}
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 poj3974 manacher算法,最大回文子串

Sample Input abcbabcbabcba abacacbaaaab END Sample Output Case 1: 13

淩亂°似流年/ 2024年02月17日 22:19/ 0 赞/ 44 阅读

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

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

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

相关 hihoCoder#1032 : 最长回文子串(manacher算法)

参考http://blog.csdn.net/xingyeyongheng/article/details/9310555 include<iostream>

╰+攻爆jí腚メ/ 2022年08月21日 00:05/ 0 赞/ 210 阅读

相关算法：最长回文子串长度

动态规划：最长回文子串：连续+回文公式 p\[i,j\] = 1)if(str\[i\] == str\[j\]) p\[i\]\[j\] = 2+p\[

冷不防/ 2022年07月26日 00:06/ 0 赞/ 218 阅读

相关最长回文串——manacher算法java实现

最长回文串是一个很好玩的话题，给出一个无序的不定长的字符序列，如何知道里面的最长回文串呢？ manacher算法的思想是 1 把偶数、奇数长的字符序列变成奇数长度 2 创

我会带着你远行/ 2022年06月10日 03:23/ 0 赞/ 255 阅读

相关 LeetCode-5. 最长回文子串（Manacher）

5. 最长回文子串 [题目描述][Link 1] -------------------- 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最

约定不等于承诺〃/ 2022年05月26日 11:43/ 0 赞/ 209 阅读

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

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

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

相关 Manacher算法解决最长回文子串问题-Java版

Manacher算法解决最长回文子串问题最长回文子串问题，就是给定一个字符串，求出字符串中最长回文子串的长度。回文串就是从头到尾遍历和从尾到头遍历是一模一样的。暴

绝地灬酷狼/ 2022年02月01日 16:25/ 0 赞/ 248 阅读

相关 Leetcode 5 最长回文子串 Manacher O(n)

python练习题,本题学习的知识点: 1.range(n,m)范围是n~m-1 2.申请一个数组 L = \[0\] \ N 申请一个N长度的Int数组,并初始值

系统管理员/ 2022年01月30日 01:53/ 0 赞/ 214 阅读

相关最长回文字串算法，Manacher

转载：[Manacher算法（最大回文子串），JAVA实现][Manacher_JAVA] 转载于:https://www.cnblogs.com/push-blackpea

红太狼/ 2021年11月01日 07:44/ 0 赞/ 310 阅读