HDU3068 最长回文 < Manacher >

Problem

最长回文

Time Limit:
Memory Limit:

Problem Description

给出一个只由小写英文字符组成的字符串, 求中最长回文串的长度.
回文就是正反读都是一样的字符串, 如, 等

Input

输入有多组,不超过组,每组输入为一行小写英文字符组成的字符串
两组之间由空行隔开(该空行不用处理)
字符串长度

Output

每一行一个整数,对应一组,表示该组的字符串中所包含的最长回文长度.

Sample Input

1
2

aaaa
abab

Sample Output

1
2

4
3

标签：Manacher

Solution

板子题。
不懂可以戳此博客。
简单来说，就是记录以每个位置为中心的回文串的半径长度，这样在后面计算的时候可以根据对称性，利用前面的结果加速，找更长匹配时暴力扩展，复杂度。由于此算法仅能对付长度为奇数的回文串（毕竟你算的是以每个点为中心的回文串），故先在每两个字符间插入一个占位符。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_L 110000
using namespace std;
char s[MAX_L*2+5];
int f[MAX_L*2+5];
int manacher (char* s0) {
    int len = strlen(s0);
    for (int i = 0; i < len; i++)	s[i*2+1] = '#', s[i*2+2] = s0[i];
    s[len = len*2+1] = '#';
    int pos = 0, r = 0, ret = 0;
    for (int i = 1; i <= len; i++) {
        f[i] = (i < r) ? min(f[2*pos-i], r-i) : 1;
        while (i-f[i] >= 1 && i+f[i] <= len && s[i-f[i]] == s[i+f[i]])	f[i]++;
        if (i+f[i] > r)	pos = i, r = i+f[i];
        ret = max(ret, f[i]-1);
    }
    return ret;
}
int main() {
    char s0[MAX_L+5];
    while (~scanf("%s", s0))	printf("%d\n", manacher(s0));
    return 0;
}