[テストケース] Suffix Array

[NokonoKotlin]

嘘解法の提出(提出 221284)

Ukkonen アルゴリズムによる Suffix Tree の構築で Suffix Link の構築をサボっても通ってしまいます。詳細な説明はできませんが、以下のケースで TLE すると思います。Suffix Link の構築をサボっている部分は提出コードの 278 行目のコメントアウトの部分です。

hack_sft.txt (追記 : 制約違反があったので修正しました)

[NokonoKotlin]

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

[maspypy]

ありがとうございます。 ・これをそのまま足す ・ついでに、単一文字から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

[NokonoKotlin]

このテストケースついてもう少し考えてみました。このテストケースの本質は 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 以外の文字) は残しておいても良いと思います。

[NokonoKotlin]

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

hack_sft_2.txt