HDU 3068 最长回文(Manacher 算法）

本文主要是介绍HDU 3068 最长回文(Manacher 算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最长回文

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5713 Accepted Submission(s): 1940

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

aaaaabab

Sample Output

4
3

题意：很明了就不多说。

思路：这题字符串长度有10W。所以用Manacher算法，时间复杂度为O(n). 具体的算法可以看看这篇博客写的，还蛮清楚的http://www.cnblogs.com/wuyiqi/archive/2012/06/25/2561063.html。

代码：

#include <stdio.h>
#include <string.h>char str[222222];
char copy[111111];
int p[222222];
int len, lens;int min(int a, int b) {return a < b ? a : b;
}
void tra() {len = strlen(copy);str[0] = 'S';lens = 0;for (int i = 1, j = 0; j < len; i ++) {if (i % 2 == 0) str[i] = copy[j ++];else str[i] = '#';lens = i;}str[++ lens] = '#';str[++ lens] = '\0';
}
int solve() {memset(p, 0, sizeof(p));int mx = 0, id = 0, Max = 0;for (int i = 1; i < lens; i ++) {if (mx > i) p[i] = min(p[2 * id - i], mx - i);else p[i] = 1;for (;str[i + p[i]] == str[i - p[i]]; p[i] ++){if (Max < p[i])Max = p[i];}if (p[i] + i > mx) {mx = p[i] + i;id = i;}}return Max;
}int main() {int bo = 0;while (~scanf("%s", copy)) {tra();solve();printf("%d\n", solve());}return 0;
}

这篇关于HDU 3068 最长回文(Manacher 算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！