HDU3068 最长回文 < Manacher >

Problem

最长回文

Time Limit: $4000/2000 MS (Java/Others)$
Memory Limit: $32768/32768 K (Java/Others)$

Problem Description

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

Input

输入有多组$case$,不超过$120$组,每组输入为一行小写英文字符$a,b,c\cdots y,z$组成的字符串$S$
两组$case$之间由空行隔开(该空行不用处理)
字符串长度$len\le 110000$

Output

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

Sample Input

aaaa
abab

Sample Output

4
3

标签：Manacher

Solution

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

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;
}