prefixとsuffix
これを機会に SA-IS を整備した！ 今回の記事はあくまで自分が読んでわかる以上を目指さない備忘録として。 問題へのリンク 問題概要 2 つの文字列 に対して「先頭何文字が一致しているか」を と表すことにします。 長さ の文字列 が与えられます。 の 文字…
ABS (AtCoder Beginner Selection) の 9 問目に選んだ問題！ 問題へのリンク 問題概要 英子文字からなる長さ の文字列 が与えられます。 をいくつかの連続する文字列に分割して、かつそれらの文字列がすべて "dream", "dreamer", "erase", "eraser" のいずれ…
こういう重たい実装を確実にこなせるように...なりたい！ 問題へのリンク 問題概要 個の文字列 が与えられる。これらを好きな順序で好きな回数だけ concat して回文を作りたい。ただし 番目の文字列を使用するコストは 1 回あたり である。 回文を作れるかど…
頑張った 問題概要 個の文字列が与えられて そのうちの指定された 個についてについては、その prefix となっている 指定されていない 個については prefix にはなっていない ような最短の文字列を求めよ。存在しない場合は -1 とせよ。 制約 個の文字列の長…
なのでいくらでも何でもできるという感覚 問題へのリンク 問題概要 すぬけ君は次の条件を満たす文字列に興味があります。 長さ 以上である。 先頭 文字が文字列 に一致する。 末尾 文字が文字列 に一致する。 条件を満たす文字列のうち、最も短いものの長さ…
今回は Suffix Array でやってみたけど、ローリングハッシュとか、KMP とか、Z-Algorithm とか、色んな方法があるみたいなので追々やってみたい。 → やってみた (3/14) 問題へのリンク 問題概要 文字列 がよい文字列であるとは「いかなる文字列 および 2 以…
こういうのちゃんと解き切れるようになりたい... なんだろ、「'a' と 'b' の個数が等しくなるような区間ごとに分割する」という発想がちゃんと出て来るようにするためには、どういう流れの考察をすればよいのだろう... 問題へのリンク 問題概要 N 個の 'a' …
