DDOSvoid's Blog

51nod 1277 字符串中的最大值

发表于 分类于
本文字数： 712 阅读时长 ≈ 1 分钟

题目描述

http://www.51nod.com/Challenge/Problem.html#problemId=1292

Solution

我们利用 $nxt$ 数组，对于每个 $pre[i]$ 来进行一次计算

每次相当于是一个前缀加，直接打个标记即可

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
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 100010
#define ll long long 
using namespace std;

int n; 

char s[maxn];

int nxt[maxn], sum[maxn]; 
void init_nxt(char *s) {
    nxt[1] = 0; int k = 0, n = strlen(s + 1);  
    for (int i = 2; i <= n; ++i) {
        while (k && s[i] != s[k + 1]) k = nxt[k];
        if (s[i] == s[k + 1]) ++k;
        nxt[i] = k; ++sum[k];
    }
}

ll ans;
int main() {
    scanf("%s", s + 1); n = strlen(s + 1); init_nxt(s); 
    for (int i = n; i; --i) sum[nxt[i]] += sum[i];
    for (int i = 1; i <= n; ++i) ans = max(ans, 1ll * i * (sum[i] + 1));
    cout << ans << endl; 
    return 0;
}