実装方針

この問題では連想配列 (C++ の std::map や python の dictionary など) と呼ばれるデータ構造が有用です． 連想配列では整数に限らない好きな値を添字として使うことができ，添字の追加・削除，特定の添字に対応する値の取得・変更などといった操作が高速に(サイズに対する対数時間などで)行えます．

本問題では，文字列を添字とする連想配列 \(memo\) をもち，添字 \(t\) に対応する値 \(memo[t]\) として \(s\) の出現回数を保持することを考えます．具体的なアルゴリズムは以下のように書けます．

• 整数 \(i = 1, \dots, N-K+1\) に対して，以下の処理を行う．
  • \(S\) の \(i\) 文字目から \(i+K-1\) 文字目までからなる部分文字列を取得し，\(t\) とおく．
  • \(memo[t]\) の値を \(1\) 増加させる．

\(memo\) が完成した後で，出現回数 \(memo[t]\) の最大値 \(ans\) を求めることを考えます．これは，初期値 \(ans = 0\) として，以下の処理をすべての添字 \(t\) に対して行うことで得られます．

• \(memo[t]\) が \(ans\) よりも大きい場合，\(ans\) の値を \(memo[t]\) で上書きする．

その後，再度すべての添字 \(t\) に対して以下の処理を行えば，出現回数が \(ans\) に一致する文字列を列挙することができます．

• \(memo[t]\) が \(ans\) と一致する場合，\(t\) を答えに追加する．

実装例 (C++)

C++ の std::map は内部的に要素を狭義の弱順序にしたがってソートします(リファレンス)．また，C++ において文字列の比較は辞書順比較による順序がデフォルトとなっています．for 構文によってその順序に沿って要素を列挙することができ，これを利用することで実装が簡便になります．

#include <iostream>
using std::cin;
using std::cout;
using std::min;
using std::max;
#include <vector>
using std::vector;
#include <string>
using std::string;
#include <map>
using std::map;


int main (void) {
	// input
	int n, k;
	string s;
	cin >> n >> k;
	cin >> s;

	// make a dictionary: memo[t] := #appearance of t
	map<string, int> memo;
	for (int i = 0; i < n-k+1; i++) {
		string t = s.substr(i, k);
		memo[t] += 1;
	}
	// find max appearance
	int vmax = 0;
	for (auto &[key, val] : memo) {
		vmax = max(vmax, val);
	}
	// list all t with max appearance (for-map lists all keys in lexicographical order)
	vector<string> vs;
	for (auto &[key, val] : memo) {
		if (val == vmax) vs.push_back(key);
	}

	// output
	cout << vmax << "\n";
	for (int i = 0; i < vs.size(); i++) {
		if (i > 0) cout << " ";
		cout << vs[i];
	}
	cout << "\n";

	return 0;
}