marimo’s blog

SA-IS(Suffix Array - Induced Sorting)をお勉強しました。 Suffix Array(SA)を線形時間で構築できるすごいやつです。 厳密な証明はめんどくさいので、省略！ｗ アルゴリズムの概要 だいたい5段階から成ります。 LMSを求める (未ソートの)LMSを使ってInduced SortしてLMS-substringをソート LMS-substring列を構成し、そのSAを構築(再帰) できたSAからLMSをソート ソートしたLMSを使ってInduced Sort 定義 未定義の言葉が沢山あるので、定義しておきます。 文字列は終端文字があるとします。 LとS 文字列\( T \)に対して、 \( T_i < T_{i+1} \)のとき、\( i \)をS-type(Smaller)、 \( T_i > T_{i+1} \) のとき、\( i \)をL-type(Larger)、 と呼びます。 \( T_i = T_{i+1} \)のときは、\( i \)のS/Lは、\( i+1 \)と等しいとします。 終端はSであると取り決めます。 LMS \( i-1 \)がLで\( i \)がSであるような\( i \)のことをLMS(Left-Most S)と呼びます。 以降、LMSと言ったときにインデックスのことだけでなく、そこから定まるsuffixを指すこともあります。 終端はLMSであると取り決めます。 LMS-substring となり合うLMSの間の連続部分文字列です。 すなわち、\( i,j \)がLMSであって、全ての\( i < k < j \)がLMSでないようなもので、 \( S_{i....

テスト $$ ax + b $$ 虚無 voidness