试题 算法训练 字串统计
标签：sub int cin html aabb 有一个 clu algo tps
问题描述
给定一个长度为n的字符串S，还有一个数字L，统计长度大于等于L的出现次数最多的子串（不同的出现可以相交），如果有多个，输出最长的，如果仍然有多个，输出第一次出现最早的。
输入格式
第一行一个数字L。
第二行是字符串S。
L大于0，且不超过S的长度。
输出格式
一行，题目要求的字符串。
输入样例1：
4
bbaabbaaaaa
输出样例1：
bbaa
输入样例2：
2
bbaabbaaaaa
输出样例2：
aa
数据规模和约定
n
S中所有字符都是小写英文字母。
提示
枚举所有可能的子串，统计出现次数，找出符合条件的那个
思路：暴力枚举 转自这里
#include
#include
#include
#include using namespace std;
typedef long long LL;
int L;
string s;
int main()
{
cin >> L >> s;
int len = s.length();
int maxx = 0; // 出现最多的次数
string ans = "";
for (int i = L; i // 枚举子串可能的长度
for (int j = 0; j + i // 子串的起始下标
{
string s1 = s.substr(j, i); // 枚举所有子串
int cnt = 0;
for (int k = 0; k + i // 再一个for循环计算每一个子串的出现次数
{
string s2 = s.substr(k, i);
if (s1 == s2) cnt ++ ;
}
// 根据题意，第一优先输出出现次数最多的
// 出现次数相同，第二优先输出长度最长的
// 长度相同，第三优先输出出现最早的
// 因为我们枚举子串的顺序，就是按照出现顺序，所以只考虑前俩即可
if (cnt > maxx) // 考虑第一优先因素：出现次数
{
maxx = cnt;
ans = s1;
}
else if (cnt == maxx) // 如果出现的次数相同，则将长度最长的字符串赋值给ans
{
int l1 = ans.length();
int l2 = s1.length();
if (l2 > l1) ans = s1; // 如果长度也相同，则默认输出第一次输出最早的。
}
}
cout endl;
return 0;
}
试题 算法训练 字串统计
标签：sub int cin html aabb 有一个 clu algo tps
原文地址：https://www.cnblogs.com/zbx2000/p/12780480.html
评论