ABC097-C - K-th Substring
与えられた文字列の部分文字列のうち辞書順でk番目のものを出力する問題です。
解法のソース
自分が思いついた解法
Submission #3501613 - AtCoder Beginner Contest 097
editorialを参考にした解法
Submission #3501551 - AtCoder Beginner Contest 097
自分が思いついた解法の考え方
以下1-indexedで考えてください。また、例としてサンプル2を使います。
atcoderandatcodeer
5
まず、文字列内の文字のポインタをすべてテーブルに入れます。ここで文字のポインタは、その文字からsの最後の文字までの文字列を意味しているため、次のようにならんでいるとみなせます。
1:atcoderandatcodeer
2:tcoderandatcodeer
3:coderandatcodeer
...
今、任意のn, mに対してn文字目から始まるm文字の部分文字列(以下s_n_m)は、n個目の文字列のm文字目までと言い換えられます。
そして、これらの文字列が辞書順になるようにポインタを並べ替えます。例で言うと、
1:andatcodeer
2:atcodeer
3:atcoderandatcodeer
4:codeer
...
といった具合です。
さて、今辞書順で一番小さい(以下、小さい)文字列はs_n_1です。何故なら、一番小さい文字列は一番小さい文字一文字の文字列であり、辞書順とは1文字目が一番小さいものを一番最初に持ってくる並べ方だからです。
次に、2番目に小さい文字列を探します。これは、1番目に小さい文字列に1文字付けくわえたものが理想的です。何故なら、1文字目を変えた文字列よりも2文字目を変えた文字列のほうが小さいからです。同様にn番目に小さい文字列もn-1番目に小さい文字列に1文字付けくわえたものが理想的となります。例で言うと
a
an
and
...
といった具合です。
しかし、このようにしていくといずれ文字列の最後まで達します。このとき、s_1_mとして作れる文字列は作り切ったことになるので、これ以降はs_2_mからs|s|mの中で最小の文字列を作ればいいということになります。これは先ほどと同様に考えればよいのですが、ここで文字列の重複を考える必要があります。具体的に言えば先頭から1つめの文字列と2つ目の文字列のi文字目までが一致していた場合、最小の文字列はi + 1文字の文字列とする必要があるということです。同様にして、3つ目の文字列についても考えていけます。例で言うと、
...
andatcodeer
at
atc
...
atcodeer
atcoder
atcodera
...
といった具合です。
このようにしてk番目に小さい文字列を求めることができます。計算量はソートがボトルネックになってO(|s|^2log|s|)となります。
補足
例えば"aa"といった文字列の場合、
1:a
2:aa
となりますが、この場合は1つ目の文字列の2文字目には実際は'\0'(<'a')が入っているため、他と同様に扱えます。
制約のとおりk<=5の場合、editorialの満点解法と上の解法を組み合わせてO(k|s|log|s|)の解法も可能だと思われます。またkの制約がない場合でも計算量がO(|s|^2log|s|+k)となるため対応できると思われます。
