Karkkainen、P. Sanders による線形時間サフィックス配列作成アルゴリズムの実装を理解しようとしています。アルゴリズムの詳細については、こちらを参照してください。
全体的なコンセプトは理解できましたが、提供された実装と一致せず、明確に把握できませんでした。
これが私を混乱させている最初のコードパスです。
紙によると：n0、n1、n2は、i mod 3 =（0,1,2）で始まるトリプレットの数を表します
コードによると: n0 = (n + 2) / 3, n1 = (n + 1) / 3, n2 = n / 3; => これらの初期化はどのように導出されたのですか?
論文によると: i mod 3 != 0 でトリプレットを連結した T` を作成する必要があります
コードによると：n02 = n0 + n2; s12 = [n02] ==> n02 はどうして？n12、つまり n1 + n2 である必要があります。
コードに従って: for (int i = 0, j = 0; i < n + (n0 - n1); i++) i%3 != 0; となるように s12 をトリプレットで埋めます。=> for ループが n + (n0 - n1) 回実行されるのはなぜですか? 単純に n1 + n2 にする必要があります。すべきではありませんか？
これらの理由により先に進むことができません :( 助けてください。