CSAcademy Max Substring
<問題概要>
文字列が与えられます。の連続する部分列のうち、その文字列の出現回数が最大のものを見つける。
ただし、そのような部分列が複数ある場合には、長さが最大のものを、
それでも複数ある場合には辞書順最小のものを答えなさい。
<解説>
a~zの26のアルファベットの出現回数のうち、最も多いものを回
とすると、答える部分文字列はすべて回現れるアルファベットで構成されます。
回以外の出現回数のアルファベットが含まれていると、部分文字列として出現回数が最大になりません。
また、すべてのアルファベットの出現回数が1の場合は単純にが答えになります。
答えるべき文字列を探索する方法ですが、に含まれる文字列はすべての出現場所でを構成している必要があります。
の最初のアルファベットを全探索し、各アルファベットごとに、文字列の2文字目のアルファベットの出現箇所が1文字目の出現箇所に比べて1増加していれば、
2文字の候補を作れます。(すべての出現箇所で連続になっているかどうかチェックします)
同様に3文字目、4文字目と作っていき、それぞれの最大文字数のうち、辞書順最小のものが答えになります。
コードではでアルファベットの番目の出現場所として、チェックしています。
また、には同じ文字は出現しないので、になります。
<コード>
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の場合でハマっていた。。。
解説の日本語が冗長ですみません。