GroupBlog

题目链接:

[kuangbin带你飞]专题十六 KMP & 扩展KMP & Manacher X - 最长回文

题目大意:

给出一个只由小写英文字符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

思路:

Manacher详解请看Manacher详解

代码:

/*************************************************************************
        > File Name: codeforces_55d.cpp
      > Author: dulun
      > Mail: dulun@xiyoulinux.org
      > Created Time: 2016年04月12日 星期二 11时01分12秒
 ************************************************************************/

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define LL long long
using namespace std;
const int N = 150086;
char a[N];
char t[N*2];
int r[N*2];

void change()
{
    int len = strlen(a);
    t[0] = '@';
    t[1] = '#';
    for(int i = 0; i < len ;i++)
    {
        t[2*i+2] = a[i];
        t[2*i+3] = '#';
    }
    t[len*2+1] = '#';
    t[len*2+2] = '\0';
}

int manacher()
{
    memset(r, 0, sizeof(r));
    int len = strlen(t);
    int ans = 1;
    int mid = 1;
    r[0] = r[1] = 1;
    for(int i = 2; i <= len; i++)
    {
        int num = min(r[2*mid-i], r[mid] + mid -i);
        while(t[i+num] == t[i-num]) num++;
        r[i] = num;
        if(i+r[i] > mid+r[mid]) mid = i;
        if(num > ans) ans = r[i];
    }
    return ans-1;
}

int main()
{
    while(~scanf("%s", a))
    {
        change();
        //printf("%s\n", t);
        printf("%d\n", manacher());
    }

    return 0;
}