51nod 1277 字符串中的最大值（kmp）

本文主要是介绍51nod 1277 字符串中的最大值（kmp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

一个字符串的前缀是指包含该字符第一个字母的连续子串，例如：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，是所有前缀中最大的。

Input

输入字符串S, (1 <= L <= 100000， L为字符串的长度)，S中的所有字符均为小写英文字母。

Output

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

Input示例

abababa

Output示例

解题思路

直接使用kmp获得next数组就可以完美解决，其中较长的前缀出现一次就代表较短的前缀也出现了num次，处理完之后递推一次。还傻傻的优化字典树/shuai……

代码实现

#include<bits/stdc++.h>
using namespace std;
#define maxn 100007
#define ll long long
char str[maxn];
ll ne[maxn];
ll num[maxn];
void getnext(int n)
{int j,k;j=0,k=-1,ne[0]=-1;while(j<n){if(k==-1||str[j]==str[k])ne[++j]=++k;else  k=ne[k];}
}
int main()
{scanf("%s",str);int n=strlen(str);ll ans=0;memset(num,0,sizeof(num));memset(ne,0,sizeof(ne));getnext(n);for(int i=n; i>0; i--){num[i]++;ans=max(ans,num[i]*(i));num[ne[i]]+=num[i];}printf("%lld\n",ans);return 0;
}