HYSBZ 2565 最长双回文串 (回文树)

2565: 最长双回文串

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 1377  Solved: 714

[Submit][Status][Discuss]

Description

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串,而abc不是(abc的顺序为“abc”,逆序为“cba”,不相同)。 输入长度为n的串S,求S的最长双回文子串T,即可将T分为两部分X,Y,(|X|,|Y|≥1)且X和Y都是回文串。

Input

一行由小写英文字母组成的字符串S。

Output

一行一个整数,表示最长双回文子串的长度。

Sample Input

baacaabbacabb

Sample Output

12

利用回文树统计以i为结尾的最长回文串长度和以i为开始的最长回文串的长度

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;
typedef long long int LL;
const int maxn=1e5+5;
char str[maxn];
struct Tree
{
    int next[maxn][26];
    int fail[maxn];
    int len[maxn];
    int s[maxn];
    int last;
    int p;
    int n;
    int new_node(int x)
    {
        memset(next[p],0,sizeof(next[p]));
        len[p]=x;
        return p++;
    }
    void init()
    {
        p=0;
        new_node(0);
        new_node(-1);
        last=0;n=0;
        s[0]=-1;
        fail[0]=1;
    }
    int get_fail(int x)
    {
        while(s[n-len[x]-1]!=s[n])
            x=fail[x];
		return x;
    }
    int add(int x)
    {
        x-='a';
        s[++n]=x;
        int cur=get_fail(last);
        if(!(last=next[cur][x]))
        {
            int now=new_node(len[cur]+2);
            fail[now]=next[get_fail(fail[cur])][x];
            next[cur][x]=now;
            last=now;
        }
        return len[last];
    }
}tree;
int s1[maxn];
int s2[maxn];
int main()
{
    while(scanf("%s",str)!=EOF)
    {
        int len=strlen(str);
        tree.init();
        memset(s1,0,sizeof(s1));
        memset(s2,0,sizeof(s2));
        for(int i=0;i<len;i++)
        {
            s1[i]=tree.add(str[i]);
        }
        tree.init();
        for(int i=len-1;i>=0;i--)
        {
            s2[i]=tree.add(str[i]);
        }
        int ans=0;
        for(int i=0;i<len;i++)
        {
            ans=max(ans,s1[i]+s2[i+1]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

BZOJ2844: albus就是要第一个出场(线性基)

已知一个长度为n的正整数序列A(下标从1开始), 令 S = { x | 1 <= x <= n }, S 的幂集2^S定义为S 所有子

852
来自专栏闻道于事

Java工具类之浮点精确计算

1142
来自专栏武培轩的专栏

京东2019春招Java工程师编程题题解

生成回文串 题目描述 对于一个字符串,从前开始读和从后开始读是一样的,我们就称这个字符串是回文串。 例如"ABCBA","AA","A"是回文串,而"ABCD"...

3088
来自专栏wym

字符串--最长回文子串(暴力讲解+Manacher)

问题描述:给你一个字符串str,若子串s是回文串,则称s为str的回文子串,求s的最大长度

2472
来自专栏Pythonista

Golang之反射(重点!!)

1562
来自专栏专注研发

poj-1503-java大数相加

One of the first users of BIT's new supercomputer was Chip Diller. He extended h...

1311
来自专栏Java帮帮-微信公众号-技术文章全总结

【编程题】Java编程题二(10道)

【编程题】Java编程题二(10道) 【程序11】 题目:有1、2、3、4四个数字,能组成多少个互不相同且无重复数字的三位数?都是多少? public c...

4009
来自专栏java达人

数字的陷阱

Java中对数字的处理,如四舍五入,如加减乘除,貌似是一个很基础很简单的知识点,但是如果你没有对他进行充分了解,很容易掉进它的陷阱里。 1、浮点数运算 先来看一...

1918
来自专栏HansBug's Lab

3097: Hash Killer I

3097: Hash Killer I Time Limit: 5 Sec  Memory Limit: 128 MBSec  Special Judge Su...

2284
来自专栏码匠的流水账

聊聊rocketmq的BrokerHousekeepingService

本文主要研究一下rocketmq的BrokerHousekeepingService

1071

扫码关注云+社区

领取腾讯云代金券