题目来源: Codility
基准时间限制:1 秒
空间限制:131072 KB 分值: 80
一个字符串的前缀是指包含该字符第一个字母的连续子串,例如: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示例
10
题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1277
分析:kmp裸题,之后会补上纯板子
下面给出AC代码:
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn=100010;
5 char x[maxn];
6 int kmpnext[maxn];
7 int len;
8 int res[maxn];///出现次数
9 void pre_kmp(char x[],int m,int kmpnext[])
10 {
11 int i,j;
12 j=kmpnext[0]=-1;
13 i=0;
14 while(i<=m)
15 {
16 if(j==-1||x[i]==x[j])
17 {
18 kmpnext[++i]=++j;
19 }
20 else
21 {
22 j=kmpnext[j];
23 }
24 }
25 return;
26 }
27 int main()
28 {
29 cin>>x;
30 len=(int)strlen(x);
31 pre_kmp(x,len,kmpnext);
32 for(int i=len;i>=1;i--)
33 {
34 res[i]++;
35 res[kmpnext[i]]+=res[i];
36 }
37 ll ans=0;
38 for(ll i=1;i<=len;i++)
39 {
40 ans=max(ans,res[i]*i);
41 }
42 cout<<ans<<endl;
43 return 0;
44 }