问题描述
给定一个长度为n的字符串S,还有一个数字L,统计长度大于等于L的出现次数最多的子串(不同的出现可以相交),如果有多个,输出最长的,如果仍然有多个,输出第一次出现最早的。
输入格式
第一行一个数字L。
第二行是字符串S。
L大于0,且不超过S的长度。
输出格式
一行,题目要求的字符串。
输入样例1:
4
bbaabbaaaaa
输出样例1:
bbaa
输入样例2:
2
bbaabbaaaaa
输出样例2:
aa
数据规模和约定
n<=60
S中所有字符都是小写英文字母。
提示
枚举所有可能的子串,统计出现次数,找出符合条件的那个
解题思路:从最短长度l依次枚举到长度为length的子串。依次比较,并记录出现次数最大,最后按照要求比较,并输出。
AC代码:#include <iostream>
#include <string>
using namespace std;
string s, ans;
int main()
{
int l;
cin >> l >> s; //子串最短长度和整个字符串
int len = s.length();
int max = 0; //出现最多的次数
for(int i = l; i <= len; i++)
{
for(int j = 0; j + i <= len; j++)
{
int cnt = 0;
string tmp1 = s.substr(j, i);//子串的长度逐渐从l增加到len ,即枚举的过程
for(int k = j; k + i <= len; k++)
{
string tmp2 = s.substr(k, i);//cnt至少出现一次。
if(tmp1 == tmp2)
cnt ++;
}
if(cnt >= max)
{
if(cnt > max)
{
max = cnt; //将出现最多的次数赋值给max
ans = tmp1;//将出现最多的字符串 赋值给ans
}
if(cnt == max) //如果出现的次数相同,则将长度最长的字符串赋值给ans
{
int l1 = ans.length();
int l2 = tmp1.length();
if(l2 > l1)
ans = tmp1;//如果长度也相同,则默认输出第一次输出最早的。此处很多同学无法理解,可以试着看看bbaabbaa这个字符串,bb,aa长度相同,出现次数相同,但是从枚举的顺序可以看出bb第一次要早于aa,所以默认ans字符串!
}
}
}
}
cout << ans << endl;
}