kou6839の日記

c++ 競プロ(特にcsacademy) linuxについて書きます。普段は自動車屋さんでナビ開発してます。転職先を探しています!!。

CSAcademy Max Substring

csacademy.com

<問題概要>
文字列{S}が与えられます。{S}の連続する部分列のうち、その文字列の出現回数が最大のものを見つける。
ただし、そのような部分列が複数ある場合には、長さが最大のものを、
それでも複数ある場合には辞書順最小のものを答えなさい。

<解説>
a~zの26のアルファベットの出現回数のうち、最も多いものを{MAXCOUNT}
とすると、答える部分文字列はすべて{MAXCOUNT}回現れるアルファベットで構成されます。
{MAXCOUNT}回以外の出現回数のアルファベットが含まれていると、部分文字列として出現回数が最大になりません。
また、すべてのアルファベットの出現回数が1の場合は単純に{S}が答えになります。

答えるべき文字列{T}を探索する方法ですが、{T}に含まれる文字列はすべての出現場所で{T}を構成している必要があります。
{T}の最初のアルファベットを全探索し、各アルファベットごとに、文字列{T}の2文字目のアルファベットの出現箇所が1文字目の出現箇所に比べて1増加していれば、
2文字の候補を作れます。(すべての出現箇所で連続になっているかどうかチェックします)
同様に3文字目、4文字目と作っていき、それぞれの最大文字数のうち、辞書順最小のものが答えになります。
コードでは{ d[i][j] }でアルファベットij番目の出現場所として、チェックしています。
また、{T}には同じ文字は出現しないので、{O(26*26*len(S))}になります。
<コード>

int main() {

	string s;
	cin >> s;
	int n = s.length();
	vi d[26];

	rep(i, n) {
		d[s[i] - 'a'].pb(i);
	}

	int max_count = 0;
	rep(i, 26) {
		max_count = max( max_count, (int)d[i].size() );
	}
	if (max_count == 1) {
		P(s);
		return 0;
	}
	string ans="";
	int max_length = -1;
	rep(i, 26) {
		if (d[i].size() != max_count) continue;
		
		int tmp_length = 0;
		while (true) {
			bool ok = true;
			rep(j, max_count - 1) {
				if (d[i][j + 1] + tmp_length >= n || s[d[i][j] + tmp_length] != s[d[i][j + 1] + tmp_length]) {
					ok = false;
					break;
				}
			}
			if (!ok)break;
			if (max_length < tmp_length) {
				max_length = tmp_length;
				ans = s.substr(d[i][0], tmp_length + 1);
			}
			else if (max_length == tmp_length) {
				ans = min(ans, s.substr(d[i][0], tmp_length + 1));
			}
			
			tmp_length++;
		}
	}
	P(ans);

	return 0;
}

<感想>
すべての文字列の出現回数が1の場合でハマっていた。。。
解説の日本語が冗長ですみません。