【AtCoder】ABC 428 B - Most Frequent Substrings

2025-10-212025-11-7

AtCoder/ABC/B問題 AtCoder/ABC/200点問題 AtCoder/灰Diff AtCoder/NoviSteps/5Q AtCoder/文字列探索/連続部分文字列 AtCoder/データ構造/連想配列(map)競技プログラミング

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 118 / NoviSteps: 5Q / 配点: 200 点

問題概要

英小文字からなる長さ $N$ の文字列 $S$ が与えられる。 $S$ の長さ $K$ の連続部分文字列の出現回数の最大値 $x$ を求め、その出現回数が $x$ となるような連続部分文字列を全て辞書順昇順に出力せよ。

制約

$N, K$ は整数
$S$ は英小文字からなる長さ $N$ の文字列
$1 \leq K \leq N \leq 100$

考察

まず、 $S$ の長さ $K$ の連続部分文字列の出現回数を、連想配列(map)を用いて数える。

次に、map を先頭から走査してvalue の最大値(これが $x$ )を求める。

その後、再度 map を先頭から走査して、value が最大値となる key を順に出力していけばよい。

$S$ の $i$ 文字目から始まる長さ $K$ の連続部分文字列は S.substr(i, K) で取得できる。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.template <typename T>
7.inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
8. 
9.// ======================================== //
10. 
11.int main()
12.{
13.    int N, K;
14.    string S;
15.    cin >> N >> K >> S;
16. 
17.    map<string, int> mp;
18.    rep(i, 0, N - K + 1)
19.    {
20.        mp[S.substr(i, K)]++;
21.    }
22. 
23.    int ans = 0;
24.    for (const auto &[key, value] : mp)
25.    {
26.        chmax(ans, value);
27.    }
28. 
29.    cout << ans << endl;
30. 
31.    for (const auto &[key, value] : mp)
32.    {
33.        if (value == ans)
34.        {
35.            cout << key << " ";
36.        }
37.    }
38.    cout << endl;
39. 
40.    return 0;
41.}