Suffix Array を用いる練習問題！ ACL practice contest にもある。 問題へのリンク 問題概要 長さが の文字列 が与えられる。 の連続する部分文字列の種類数を答えよ。 制約 考えたこと 実は、AtCoder Library Practice Contest に全く同じ問題がある！ drk…

Suffix Tree 上で DFS した。デバッグがめっちゃ大変だった！ 問題へのリンク 問題概要 個の英小文字からなる文字列 が与えられる。 これら 個の文字列について、連続する部分文字列をすべて考える。重複を除かずに考えると 個ある。 これら 個の文字列を辞…

文字列の連続した部分文字列を数え上げるのは Suffix Array の典型問題。それを少し応用した面白い問題！ 問題へのリンク 問題概要 英小文字からなる 2 つの文字列 が与えられる。次の条件を満たす文字列の個数を求めよ。 中に連続した部分文字列として含ま…

Suffix Array の典型問題 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。 の連続する部分文字列として登場しうる文字列をすべて考える。重複は除外する。これらの文字列の長さの総和を求めよ。 制約 考えたこと 次の問題とほと…

めっちゃ面白い問題だった！ Suffix Array の練習問題。 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。 の suffix は空文字列を除いて 個ある。これらの suffix を適切な順序で連結させて 1 つの文字列を作るとき、それが辞書順最…

Suffix Array と LCP の理解を問う問題。超シンプルで面白い問題！ 問題へのリンク 問題概要 長さが の文字列 が与えられる。 の連続する部分文字列の種類数を答えよ。 制約 解法 文字列 の Suffix とは「後ろの何文字かをとってできる文字列」のことである…

これを機会に SA-IS を整備した！ 今回の記事はあくまで自分が読んでわかる以上を目指さない備忘録として。 問題へのリンク 問題概要 2 つの文字列 に対して「先頭何文字が一致しているか」を と表すことにします。 長さ の文字列 が与えられます。 の 文字…

文字列検索に関するライブラリが充実していれば怖いものがない。でも文字列のことを知らなくても実は DP でも解ける！！！ Suffix Array Z-algorithm (editorial 解) ロリハ + 二分探索 「ロリハ + 二分探索」の高速化 (editorial のラスト 3 行で言及された…

詰め切るの大変だった！ 問題へのリンク editorials 問題概要 '0'〜'9' からなる長さ の文字列 が与えられる。 これらの文字列をいくつかの連続する部分文字列に分ける。次の条件を満たす必要がある。 各部分文字列を数値とみなしたとき、strictly に単調増…