arrayを作った後に、隣り合う項目同士の最長共通プレフィックスを求めておくやつです。隣同士の最長共通プレフィックスのリストがあると、あとはRMQとか使えば任意の2つのサフィックスの共通プレフィックスが求められたりして便利(らしい)です。かかります...よね*1。arrayで通しているというのです。arrayが構築できる方法について調べてみました。上級者の皆様には「そんな事も知らなかったのか」「蟻本(上級編)に書いてあるぞ」「蟻本読め」「蟻本」と思われることでしょうが青コーダーレベルだと今までそれで困る場面がなかったということでお許しください。Array2009年に出てきたSA-ISというのが現在最強らしいです。蟻本にも名前は出てきます。(p.337)なお、接尾辞配列を構成するアルゴリズムは他にも多数存在しています。SA-ISと呼ばれるアルゴリズムなど、線形時間で非常に高速に構成するアルゴリズム等も存在していますが、プログラミングコンテストではほとんどの場合で上のアルゴリズム*3で十分です。Induced-Sorting論文にCで書かれたコードが載ってます(そのまま動きます)。仕組みについては日本語で書かれた解説記事があります。賢いアルゴリズムです。(Rubyで書いてある)これを使うとSPOJのSARRAYで満点が取れるらしいです。(※まだ試してない)実装は元論文に載っているCで書かれたコードがそのまま動きます*5。Moriさんによる実装などもあります。求めることができるのです。なんということでしょう!(※蟻本のpp.339-340にもあります。蟻本を斜め読みしかしていないかが分かります。Python)LCPが1以上の2つのサフィックスがあるときに、それぞれの2文字目以降のサフィックス同士のLCPは元の2つのサフィックスのLCPより1つ小さいという事実を使って計算量を節約することができるというアイデアです。arrayが構築できてしまいます。線形時間で構築する問題を解くことができました。いかがでしたか?*1:蟻本上級編を読めというお叱りはあとで受けます。*2:毎週日曜開催の某コンテストで最近そんな問題が出ました。Myersのアルゴリズム。char)を渡します。サンプル入出力などこちらから入手可能です。»@naoya_t自然言語処理とか機械学習とか競技プログラミングとか。競プロ精進記録は別ブログ🔒に移しました。yukicoder遅延伝搬セグメント木の復習をしたので、beetさん作問のセグ木コンテスト(2019/9/6開催)の問題を解いてみた。サウスタワー23Fなんで自分に参加権が来たのかよく分からないオンサイトイベントに参加してきた話。146のQ4でN個の点の3次元マンハッタン距離の最大値を求める問題が出たのでメモ。"なお、接尾辞配列を構成するアルゴリズムは他にも多数存在しています。14:00-FORCIAさんで開催されたオンサイトのゆるふわコンテストに参加。過去問コンテスト後に読んだ問題たち。ここで出てくるテクニックもこの機会にぜひ身につけておきたい。