题解 [email protected]洛谷 【[Cnoi2020]子弦】

求一个字符串出现次数最多的非空子串。


思路:

容易想到,这个子串肯定要尽量短,一个字母是最优的。

因为假如子串 ab 的出现次数为 kk,那么在这个字串中,ab 各自分别已经出现了 kk 次,因此这两个的出现次数一定不小于 ab,甚至可能还要多。

因此题面转化为,求字符串中出现次数最多的字母。我们考虑使用 map 进行统计,利用迭代器遍历即可。(比赛时没注意到只有小写字母,因此用了迭代器)


代码:

//By: [email protected]_er(122461)
#include <bits/stdc++.h>
using namespace std;

map<char, int> mp;
string s;

int main() {
	cin>>s;
	int l = s.length(); 
	for(int i=0;i<l;i++) ++mp[s[i]];
	int ans = 0;
	for(map<char,int>::iterator iter=mp.begin();iter!=mp.end();++iter) ans = max(ans, iter->second);
	printf("%d\n", ans);
	return 0;
}