naoya_t@hatenablog

いわゆるチラシノウラであります

Suffix Array(接尾辞配列)とLCP(最長共通接頭辞)arrayを線形時間で構築する方法を調べてみた 〜SA-ISとKasai's algorithm〜

suffix arrayは知ってます。(当然)
(知ったきっかけは何だったかな…高林さんのsaryかな)
以前、英辞書検索用のCLIツールを作る時などにも使いました。

でも今までずっと、文字列のポインタを1つずつずらした(文字列の長さ分の)char**配列を用意してqsortでstrcmp的なものを渡すような、愚直な(O(N^2\log N)の)書き方しかしたことがありませんでした。

あまりそれで困るような場面に遭遇したことがなかったということでもありますが、
競プロで使うとなるとそういうわけにはいきません。

制約がN=|S|=10^5とかだともう無理ですよね。

LCP(最長共通プレフィックス)array もそうです。
suffix arrayを作った後に、隣り合う項目同士の最長共通プレフィックスを求めておくやつです。
隣同士の最長共通プレフィックスのリストがあると、あとはRMQとか使えば任意の2つのサフィックスの共通プレフィックスが求められたりして便利(らしい)です。
(配列の長さ-1)組の文字列の比較なので普通に考えたらO(N^2)かかります…よね*1

なのに、N=10^5なのにいかにもsuffix arrayとLCP(最長共通プレフィックス)arrayを計算して下さいと言わんばかりの問題*2が来て、上位陣はsuffix arrayで通しているというのです。

そこで

  • O(N)でLCP arrayが構築できる方法

について調べてみました。

上級者の皆様には「そんな事も知らなかったのか」「蟻本(上級編)に書いてあるぞ」「蟻本読め」「蟻本」と思われることでしょうが青コーダーレベルだと今までそれで困る場面がなかったということでお許しください。

*1:蟻本上級編を読めというお叱りはあとで受けます。

*2:毎週日曜開催の某コンテストで最近そんな問題が出ました。

続きを読む

LeetCode Weekly Contest 136

5/12(日) 11:30-13:00
とあるTully'sにて
Dを通せないまま途中離脱(3完1ペナ);
143/4109位
3完の割にひどい順位にならなかったのはQ4通した人数が少なかったから(全完92人)
それでもレートは微増:2306→2309
f:id:n4_t:20190514121829p:plain:w320
World Rankingは144 / 95530

D問題絡みでSuffix ArrayとLCPを線形時間で構築する方法を学んだ。

続きを読む

diverta 2019 Programming Contest

atcoder.jp
5/11(土) 21:15-23:15
1ペナ4完で286位
終了12分前にEを提出したけれどジャッジが詰まっててそのまま終了
(結局TLEだったので4完のまま)
ジャッジ詰まりまくって結局unratedになった。(折角2000超えパフォだったので残念)

続きを読む

Codeforces Round #558 (Div. 2)

れじってたけど出なかった(=寝落ちした)回
A-B1/B2-C1/C2まで解いた
Dは考えたけど計算合わない
(所要時間とWA数から概算すると、出てたらレート±0ぐらいかな…)
あとでEditorialを読む

続きを読む