Suffix Automaton（SAM）の学習ノートと問題解決記録
Suffix Automaton についての概要
Suffix Automaton（SAM）は文字列アルゴリズムであり、部分文字列に関する問題を効率的に解くことを可能にします。
例えば：
異なる部分文字列の数
辞書順で第 \(k\) 番目の部分文字列
前提知識：
AC自動機
サフィックス配列（学ぶ必要はない）
複数の文字列を扱う際にはどのようなアルゴリズムがありますか？
最も基本的な手法は tri ...
7月30日 17:52 投稿
Manacherアルゴリズムによる回文解析の効率的処理
問題の背景
文字列 s が与えられ、その中にある最長の連続する回文部分文字列の長さを求めたいとします。単純なアプローチとしては、すべての部分文字列を列挙し、それぞれが回文かどうかを判定する方法がありますが、これは O(n^3) の計算量となり非効率です。
より良い方法として、各位置を中心として左右に拡張していく O(n^2) アルゴリズムが考えられます。この方法で ...
6月8日 23:54 投稿
接尾辞配列とその応用
接尾辞配列
単一文字列の部分文字列に関する辞書順問題に一般的に利用できます。
アルゴリズムの流れ
まず、文字列のすべての接尾辞をソートします。
定義：\(sa[i]\) はすべての接尾辞をソートした後、第 \(i\) 番目に小さい接尾辞のインデックスを表します。\(rk[i]\) は接尾辞 \(i\) のランクを表します。
倍増法と基数ソート（\(O(n\log n)\)）を採用します（簡略化/エ ...
5月23日 21:50 投稿