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
コード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]] = S[SA[i+1]]とすることができる。この条件を満たさない個数を数えることで答えが求められる。
計算量2
O(N)
