COGS 2566. [51nod 1129] 字符串最大值

★★★ 输入文件：string_maxval.in 输出文件：string_maxval.out 简单对比
时间限制：1 s 内存限制：256 MB

【题目描述】

一个字符串的前缀是指包含该字符第一个字母的连续子串，例如：abcd的所有前缀为a, ab, abc, abcd。

给出一个字符串S，求其所有前缀中，字符长度与出现次数的乘积的最大值。

例如：S = "abababa" 所有的前缀如下:

"a", 长度与出现次数的乘积 1 * 4 = 4,

"ab",长度与出现次数的乘积 2 * 3 = 6,

"aba", 长度与出现次数的乘积 3 * 3 = 9,

"abab", 长度与出现次数的乘积 4 * 2 = 8,

"ababa", 长度与出现次数的乘积 5 * 2 = 10,

"ababab", 长度与出现次数的乘积 6 * 1 = 6,

"abababa", 长度与出现次数的乘积 7 * 1 = 7. 其中"ababa"出现了2次，二者的乘积为10，是所有前缀中最大的

【输入格式】

输入字符串T, (1 <= L <= 1000000， L为T的长度)，T中的所有字符均为小写英文字母。 (注意:原题是L <= 10W，这里加强一下!)

【输出格式】

输出所有前缀中字符长度与出现次数的乘积的最大值。

【样例输入】

abababa

【样例输出】

【提示】

【来源】

kmp的next数组

用res[i]记录长度为i的前缀出现的次数显然res[len]=1;

由于Next[i]记录的是[0,i]中后缀与前缀重复的最长长度,那么长的前缀出现短的前缀也会出现 ,那么只需O(n)统计一下就好

51nod上需要I64d才能过

屠龙宝刀点击就送

#include <iostream>

#include <cstring>

#include <cstdio>

#define N 1000100

using namespace std;

char str[N];

int res[N],Next[N],len;

void Get_Next()

{

    int i=,j=-;

    Next[i]=j;

    for(;i<len;)

    {

        if(j==-||str[i]==str[j])

        {

            i++;

            j++;

            Next[i]=j;

        }

        else j=Next[j];

    }

}

int main()

{

    freopen("string_maxval.in","r",stdin);

    freopen("string_maxval.out","w",stdout);

    scanf("%s",str);

    len=strlen(str);

    Get_Next();

    for(int i=len;i>=;i--)

    {

        res[i]++;

        res[Next[i]]+=res[i];

    }

    long long Maxn=;

    for(long long i=;i<=len;i++)

    Maxn=max(Maxn,res[i]*i);

    printf("%I64d ",Maxn);

    return ;

}

巴特西