HDU 3068 最长回文（Manacher）

最新推荐文章于 2021-07-30 20:25:25 发布

ToRe.

最新推荐文章于 2021-07-30 20:25:25 发布

阅读量177

点赞数

分类专栏： Manacher 文章标签： Manacher

本文链接：https://blog.csdn.net/j2_o2/article/details/81475631

版权

Manacher 专栏收录该内容

1 篇文章

订阅专栏

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

aaaa
abab

Sample Output

4
3

Manacher板子题，记录板子，还看到了回文树算法，先点基础技能有空再看(ಥ_ಥ)

代码

#include<stdio.h>
#include<string.h>
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)

char s1[110005], s2[220005]; // 开双倍数组
int p[220005], n; // p数组记录每点的回文长度， n记录数组长度

int manacher()
{
    int mx = 0, id, ans = 0;
    for(int i = 1; i <n; ++i)
    {
        if(mx > i) p[i] = min(p[2*id-i], mx-i);
        else p[i] = 1;
        while(s2[i+p[i]] == s2[i-p[i]]) ++p[i];
        if(p[i]+i > mx) mx = p[i]+i, id = i;
        if(p[i] > ans) ans = p[i];
    }
    return ans;
}

void init() // 使字符长度变为两倍
{
    s2[0] = s2[1] = '#';
    for(int i = 0; i < n; ++i) s2[(i<<1)+2] = s1[i], s2[(i<<1)+3] = '#';
    n = (n<<1)+2;
    s2[n] = '?';
}

int main()
{
    while(~scanf("%s",s1))
    {
        n = strlen(s1);
        init();
        printf("%d\n",manacher()-1);
    }
    return 0;
}