题解：子弦

题意简述

给定一个仅包含小写字母的字符串 (S)，求 (S) 中出现次数最多的非空子串的出现次数。

核心思路：贪心优化

这道题的最优解不是复杂的 DP 或字符串算法，而是一个简单的贪心策略：

长度为 1 的子串中出现次数最多的，一定是所有子串中出现次数最多的。

推理过程

1. 长度为 1 的子串：就是单个字符，其出现次数可以直接用桶排序统计。
2. 长度 ≥ 2 的子串：任何一个长度为 (k) 的子串，其出现次数一定不超过它的第一个字符的出现次数。
   • 例如：在字符串 abababab 中，子串 ab 出现了 4 次，而字符 a 出现了 4 次，两者次数相同。
   • 再如：子串 aba 出现了 3 次，小于 a 的出现次数。
3. 结论：所有更长的子串，其出现次数都无法超过出现次数最多的单个字符。因此，问题简化为统计出现次数最多的字符的次数。

算法实现

用桶排序统计每个小写字母的出现次数，取最大值即可。

C++ 参考代码

#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;
}