[テストケース] Suffix Array about library-checker-problems HOT 4 OPEN

想定アルゴリズムと異なるので微妙な話かもしれませんが、Z-algorithm などの他の部分文字列系の問題にも Suffix Tree を使えるので、それらにも対応が必要かもしれません。

from library-checker-problems.

ありがとうございます。
・これをそのまま足す
・ついでに、単一文字から10か所程度ランダム変更したものを足してもいいかな。

参考
S.size() = 499981
i = 7122 S[i] = s
i = 249980 S[i] = g
i = 374980 S[i] = s
i = 437480 S[i] = w
i = 468730 S[i] = o
i = 484355 S[i] = q
i = 492167 S[i] = v
i = 496073 S[i] = k
i = 498026 S[i] = h
i = 499003 S[i] = p
i = 499491 S[i] = d
i = 499735 S[i] = z
i = 499857 S[i] = g
i = 499918 S[i] = a
i = 499949 S[i] = l
i = 499964 S[i] = z
i = 499972 S[i] = z
i = 499980 S[i] = p

from library-checker-problems.

このテストケースついてもう少し考えてみました。このテストケースの本質は i = 7122 S[i] = s の部分と、大量に t が存在することなので、他の単一文字はなんでも良いです。
i = 7122 S[i] = s の i が計算量の大事な部分になっていて、i は $S$ の前半である必要があり、前すぎても中間に近すぎてもダメっぽいです。例えば今回だと i = 100000 S[i] = s でもハックできます。

また、i = 499980 S[i] = p をなくしてしまうと、(Suffix Array の計算ができない形の) Suffix Tree の構築はできてしまうので 、i = 499980 S[i] = p (s,t 以外の文字) は残しておいても良いと思います。

from library-checker-problems.

i = 124000 S[i] = s としたテストケースも追記しておきます。

hack_sft_2.txt

from library-checker-problems.