きままにものづくり

日々の気付いたことなんかを書いてます。

SRM630Div1Medium

問題

ある文字列abcaのインデックスiに応じた接尾辞を考える。例としてs[0] = abca、s[1] = bcaとなる。
全ての接尾辞を列挙し、辞書順に並べ替えたインデックスをSAとする。abcaの場合は、SA = {3, 0 , 1, 2}となる。
SAとなる文字列の中で、最小の違う文字の数を求めよ。

解法1

文字列のサイズをNとすると、N個の文字を使えば必ずSAとなる文字列を再現することができる。理解しやすくするために、文字を数字とする。SA = {3, 0, 1, 2}の場合は、S=1230となる。
これを最悪のケースとして、各要素に対して引き算をしていき、操作できなくなるまで操作を続ける。

計算量1

O(N^3 log N)

コード1


解法2

解法1と同様の方法で最悪のケースSを作成する。この時、s[SA[i]] < s[SA[i+1]]を満たしている。s[i]は接尾辞を示す。S[SA[i]] = S[SA[i+1]]かつs[SA[i]] < s[SA[i+1]]という条件を増やすことで、文字の違いを減らすことができる。Sでは全ての数字が異なるのでS[SA[i] + 1] \leq S[SA[i+1] + 1]  を満たすときS[SA[i]] = S[SA[i+1]]とすることができる。この条件を満たさない個数を数えることで答えが求められる。

計算量2

O(N)

コード2

広告を非表示にする