51nod 1277 字符串中的最大值 题解

发表于 | 更新于 | 阅读次数：
本文字数： 10 字 | 阅读时长 ≈ 1 分钟

题意简述

给定一个长度的字符串，请你求出所有前缀中，出现次数乘以前缀长度的最大值。

思路框架

求一遍然后，求的最大值。

具体思路

前缀的出现次数？？自动机？

但是如果要一个一个弄的话，无论如何都要。那咋整嘛。

考虑前缀的一次出现。有什么规律？

如图。红色部分为一个长度为的前缀，在的某个位置出现了。

然后就说明，在蓝色部分，长度为的前缀=后缀。

前缀=后缀？有点熟悉呢。联想到中的数组。是前缀个中，最长的前缀=后缀的长度。我们取,直到取到为止，就是前缀个中所有前缀=后缀的长度了。而且珂以证明，如果我们像这样一个点不断取来枚举每个前缀的出现次数，显然

  1. 不会少算
  2. 不会多算

那么，设表示长度为的前缀在中出现的次数。我们枚举一个，然后不断取，对于每个，。

这样的复杂度看起来不错。但是，如果中全是一个字符a，容易证明，这个算法退化了，变成。

那咋整嘛。一眼看去好像不行了。然鹅，在仔细看一眼，就会发现一个很显然的优化：把的初始值设成，然后从到枚举，，就解决了。这个优化的核心就在于，我们用代替，就省得每次跑一遍了。

实现注意

  1. 开longlong
  2. 数组名不要叫next，会重名的

代码

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
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 155555
    #define int long long 
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)

    char s[N];
    int n;
    void Input()
    {
        scanf("%s",s+1);
        n=strlen(s+1);
    }
    int nxt[N];
    void GetNext()
    {
        nxt[1]=0;
        F(i,2,n)
        {
            int j=nxt[i-1];
            while(j and s[j+1]!=s[i]) j=nxt[j];
            if (s[j+1]==s[i]) ++j;
            nxt[i]=j;
        }
    }
    int dp[N];
    void Soviet()
    {
        GetNext();
        D(i,n,1) dp[i]=1;
        int ans=-1;
        D(i,n,1)
        {
            ans=max(ans,dp[i]*i);
            dp[nxt[i]]+=dp[i];
        }
        printf("%lld\n",ans);
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
    #undef int //long long 
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w