概要
円環や循環シフトが絡む問題は、もととなる列を つ繋げて考えることで見通しがよくなることがあります．
問題原案：achapi
解説
長さ の数列 を次のように定めます：
- ．
すると，この問題は次のように言い換えることができます：
- の相異なる長さ の連続部分列であって，辞書順で 番目に小さいものを求めよ．
また，正整数 に対して を次のように定めます：
辞書順の定義を考えると， ならば であるので， が相異なるとすると， のうち 番目に小さいものを求める問題に帰着されます．
この問題は，たとえば Suffix Array を用いることで， 時間などで解決できます．
また， ならば と の最長共通接頭辞の長さは 以上であるので，たとえば LCP Array を考えることで， なる を除外することができます．詳しくは実装例もご参照ください．
解説：uni_kakurenbo