自动搬运

查看原文

来自洛谷，原作者为

	超级玛丽王子 AFO

搬运于2025-08-24 22:24:25，当前版本为作者最后更新于2020-09-23 11:47:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

或许更好的阅读体验

这道题比赛的时候不小心漏了标签……导致很多人都知道了贪心做法。

第一眼望过去，以为这道题是 DP。DP 没想出来只好暴力枚举子串 KMP。后来看到标签突然灵光一闪，可以按照如下思路贪心：

1. 首先考虑子串长度为 $1$ 的情况。这类子串就是 $\texttt{a-z}$ 的字符。那么出现次数最多的子串就是出现次数最多的字符，简单桶排解决。

2. 接下来考虑子串长度为 $2$ 的情况。这类子串一定由某一个第一类子串加一个新字符组成。这意味着出现次数最多的这类子串出现次数一定不会比出现次数最多的一类字串多。 可以理解为一个这类子串的第一个字符出现次数不少于这个子串的出现次数。

   例如：字符串 abababab 中，ab 是一个这类子串。而 a 出现的次数一定不会比 ab 出现次数少。

3. 以此类推，长度为 $k$ 的子串出现次数一定不比其第一个字符出现次数多。

由此我们就得到了我们的贪心策略：单个字符的子串中出现次数最多的一定是所有子串中出现次数最多的。

具体实现很简单，桶排即可。代码如下：

#include <bits/stdc++.h>
using namespace std;
char s[10000005];
int cnt[27];
int mx;
int main(void) {
    scanf("%s",s);
    int slen=strlen(s);
    for(int i=0;i<slen;i++) cnt[s[i]-'a']++;
    for(int i=0;i<26;i++) if(cnt[i]>mx) mx=cnt[i];
    printf("%d",mx);
    return 0;
}

当然你也可以边 getchar 边判断。

完结撒花~ 求赞求互关QAQ