最长回文子串_Manacher算法_hihoCoder1032

题目:

http://hihocoder.com/problemset/problem/1032

时间限制: 1000ms 单点时限: 1000ms 内存限制: 64MB

描述

   小Hi和小Ho是一对好朋友，出生在信息化社会的他们对编程产生了莫大的兴趣，他们约定好互相帮助，在编程的学习道路上一同前进。

   这一天，他们遇到了一连串的字符串，于是小Hi就向小Ho提出了那个经典的问题：“小Ho，你能不能分别在这些字符串中找到它们每一个的最长回文子串呢？”

   小Ho奇怪的问道：“什么叫做最长回文子串呢？”

   小Hi回答道：“一个字符串中连续的一段就是这个字符串的子串，而回文串指的是12421这种从前往后读和从后往前读一模一样的字符串，所以最长回文子串的意思就是这个字符串中最长的身为回文串的子串啦~”

   小Ho道：“原来如此！那么我该怎么得到这些字符串呢？我又应该怎么告诉你我所计算出的最长回文子串呢？

   小Hi笑着说道：“这个很容易啦，你只需要写一个程序，先从标准输入读取一个整数N（N<=30)，代表我给你的字符串的个数，然后接下来的就是我要给你的那N个字符串（字符串长度<=10^6)啦。而你要告诉我你的答案的话，只要将你计算出的最长回文子串的长度按照我给你的顺序依次输出到标准输出就可以了！你看这就是一个例子。”

样例输入

3
abababa
aaaabaa
acacdas      

样例输出

7
5
3      

代码:

/*************************************************************************
 *  > File Name: manacher.cpp
 *  > Author: Li Zeyan
 *  > Mail: [email protected]
 *  > Created Time: 2015年10月08日 星期四 20时56分01秒
 *************************************************************************/
#include <stdio.h>
#include <string.h>
using namespace std;

inline int min (int a, int b)//求取a,b的最小值
{
    return a < b ? a : b;
}
int f[5000050];//存储每个位置为中心的最长回文子串的半长.即从中心到边界的字符数
int manacher (char s[], int length)//计算回文串长度
{
    memset (f, 0, length * 4);
    int p = 0;//p表示使得成为回文串部分的右界最大的字符的秩(rank)
    int m = -1;//m表示当前最大的回文串长度
    for (int i = 0; i < length; ++i)
    {
        if (p + f[p] > i)//f[p] >= p, 所以下面(p << 1) - 1保证有意义
            f[i] = min (f[(p << 1) - i], p + f[p] - i);//核心方程
        else
            f[i] = 1;
        while (i - f[i] >= 0 && i + f[i] < length && s[i-f[i]] == s[i+f[i]])//在上一步基础上向两边遍历,直到不相等
            ++f[i];
        if (i + f[i] > p + f[p])//更新p,如果当前字符为中心的回文串向右拓展了,就把p更新为i
            p = i;
        if (f[i] > m)//更新最大值
            m = f[i];
    }
    return m - 1; //m是半长,可以归纳得出m-1总是源字符串的最长回文子串的实际长度
           

}
char s[2000000];
int main ()
{
    //freopen ("manacher.txt", "r", stdin);
    //freopen ("manacher1.txt", "w", stdout);
    setvbuf (stdin, new char[1 << 25], _IOFBF, 1 << 25);
    setvbuf (stdout, new char[1 << 25], _IOFBF, 1 << 25);
    int n;
    scanf("%d\n", &n);
    while (n--)
    {
        char l[2000000] = {0};
        scanf("%[^\n]", l);
        getchar();//处理换行符,scanf是不读入换行符,把它留在缓冲区,cin是直接抛弃换行符(从缓冲区拿走).
        int length = strlen(l);
        s[0] = '$';
        for (int i = 0; i < length; ++i)
        {
            s[(i << 1) + 1] = '#';
            s[(i << 1) + 2] = l[i];
        }
        s[(length << 1) + 1] = '#';
        printf("%d\n", manacher(s, (length << 1) + 2));
    }
    return 0;
}
           

算法解析:

这里计算最长回文子串的基本方法就是依次枚举每一个字符,然后以这个字符为中心枚举可能的最长回文串长度. manacher所做的就是计算出在每一个字符开始枚举回文串长度的起点,从而减少枚举次数. 看一下核心方程:

<span style="white-space:pre">		</span> f[i] = min (f[(p << 1) - i], p + f[p] - i);//核心方程
           

f[(p << 1) - 1] 即 f[2p - i]给出i以p为对称轴的对称位置的回文串长度.之前对称位置的匹配和轴点的匹配就可以确定当前点是否匹配,不需要进行比较.

eg: rank 1 2 3 4 5 6 7 8

char c b c a c b c a

这里p = 4, f[p] = 5, i = 6., (p << 1) - i = 2, f[(p << 1) - i] = 2.因为从1~7都是4所"管辖"的回文串,所以1 == 7, 3 == 5, 所以如果1,3匹配,则对称的5和7匹配.

p + f[p] - i给出当前右界最靠右的回文串的右边界到当前点的距离,因为超过"统治区域"的部分没有对称性,不能判断.

manacher的另一个核心在于往原始字符串之间添加特殊符号,这样无论是奇数还是偶数的回文串就都有了轴点

eg: aaaa -> #a#a#a#a#

时间复杂度分析:

每一次匹配都是在p + f[p]右侧开始进行.而这个值之多从0变到字符串长度那么长.所以时间复杂度为O(n)