字符串最大值(题解)

#题目描述


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

这里写图片描述

#题解
题目意思很明白了。看到“前缀”,“次数”等词都很容易想到用KMP做
首先我们先回忆一下next数组的定义:next[i]表示以i结尾的非前缀子串与文本串前缀匹配的最大长度,理解了next数组的定义这个题目就变得的简单了,我们枚举匹配的长度,用递归思想对所有的相关位置进行累加,即在$while(j) j=next[j] $这条链上做一个累加就好。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//By Bibi
/// .-~~~~~~~~~-._ _.-~~~~~~~~~-.
/// __.' ~. .~ `.__
/// .'// \./ \\`.
/// .'// | \\`.
/// .'// .-~"""""""~~~~-._ | _,-~~~~"""""""~-. \\`.
/// .'//.-" `-. | .-' "-.\\`.
/// .'//______.============-.. \ | / ..-============.______\\`.
/// .'______________________________\|/______________________________`.
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
const int MAXN=1000010;
char s[MAXN];
int len;
int next[MAXN];
int a[MAXN];
int maxx;
void init(){
scanf("%s",s+1);
len=strlen(s+1);
}
void yuchuli(){
int j=0;
next[1]=0;
rep(i,2,len){
while(j&&s[j+1]!=s[i]) j=next[j];
if(s[i]==s[j+1]) ++j;
next[i]=j;
}
}
void work(){
dep(i,len,1){
a[i]++;//对于其本身肯定有一个匹配
a[next[i]]+=a[i];//递归
}
rep(i,1,len){
maxx=max(maxx,a[i]*i);
}
printf("%d",maxx);
}
int main(){
init();
yuchuli();
work();
return 0;
}