HYSBZ 3676 回文串 (回文树)

3676: [Apio2014]回文串

Time Limit: 20 Sec  Memory Limit: 128 MB

Submit: 1680  Solved: 707

[Submit][Status][Discuss]

Description

考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出  现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最  大出现值。 

Input

输入只有一行,为一个只包含小写字母(a -z)的非空字符串s。 

Output

输出一个整数,为逝查回文子串的最大出现值。 

Sample Input

【样例输入l】 abacaba 【样例输入2] www

Sample Output

【样例输出l】 7 【样例输出2] 4

回文树模板题

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

using namespace std;
typedef long long int LL;
const int maxn=3e5+10;
char str[maxn];
struct Tree
{
    int next[maxn][26];
    int fail[maxn];
    int num[maxn];
    LL cnt[maxn];
    int len[maxn];
    int s[maxn];
    int p;
    int n;
    int last;
    int new_node(int x)
    {
        memset(next[p],0,sizeof(next[p]));
        cnt[p]=0;
        num[p]=0;
        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;
            num[now]=num[fail[now]]+1;
            last=now;
        }
        cnt[last]++;
    }
    void count()
    {
        for(int i=p-1;i>=0;i--)
            cnt[fail[i]]+=cnt[i];
    }
}tree;
int main()
{
    while(scanf("%s",str)!=EOF)
    {
        int len=strlen(str);
        tree.init();
        for(int i=0;i<len;i++)
            tree.add(str[i]);
        tree.count();
        LL ans=0;
        for(int i=2;i<tree.p;i++)
            ans=max(ans,(LL)tree.cnt[i]*tree.len[i]);
        printf("%lld\n",ans);
    }
    return 0;
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

HDU 2502 月之数(二进制,规律)

月之数 Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/...

3414
来自专栏个人分享

Socket与Http方式解析发送xml消息封装中间件jar包

  最近项目代码中太多重复的编写Document,不同的接口需要不同的模板,于是重写提取公共部分打成jar包,方便各个系统统一使用~

1563
来自专栏高性能服务器开发

(三)dict哈希结构3

/* This function performs just a step of rehashing, and only if there are * no...

2778
来自专栏小樱的经验随笔

POJ 2492 A Bug's Life

A Bug's Life Time Limit: 10000MS Memory Limit: 65536K Total Submissions:...

28910
来自专栏算法修养

PAT 1012 The Best Rank

1012. The Best Rank (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B ...

3044
来自专栏ml

HDUOJ------Lovekey

Lovekey Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (J...

2879
来自专栏Golang语言社区

提高 golang 的反射性能

golang 的反射很慢。这个和它的 api 设计有关。在 java 里面,我们一般使用反射都是这样来弄的。 ---- Field field = clazz....

5085
来自专栏HansBug's Lab

2301: [HAOI2011]Problem b

2301: [HAOI2011]Problem b Time Limit: 50 Sec  Memory Limit: 256 MB Submit: 1737...

2575
来自专栏HansBug's Lab

1257: [CQOI2007]余数之和sum

1257: [CQOI2007]余数之和sum Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 2001  So...

2918
来自专栏mukekeheart的iOS之旅

No.012 Integer to Roman

 12. Integer to Roman Total Accepted: 71315 Total Submissions: 176625 Difficulty...

2479

扫码关注云+社区

领取腾讯云代金券