AC 自動機の基礎と応用
AC 自動機は、複数のパターン文字列を効率的に検索するためのアルゴリズムです。この記事では、その基本的な構造と動作原理について説明します。
前提知識
AC 自動機を理解するためには、まずは字典木（Trie木）とKMPアルゴリズムの概念を理解しておく必要があります。
問題設定
KMPアルゴリズムは単一のパターン文字列に対する文字列マッチングを行いますが、複数のパター ...
6月28日 23:12 投稿
KMPアルゴリズムにおけるnext配列の最適化手法
KMPアルゴリズムのnext配列最適化
KMP（Knuth-Morris-Pratt）アルゴリズムでは、パターン文字列の部分一致情報を格納したnext配列を用いて、主文字列との照合時に不要な比較をスキップする。しかし、標準的なnext配列には冗長な比較が含まれる場合があるため、これをさらに最適化することが可能である。
最適化が必要なケース1
例えば、パターン文字列の先頭文字と現在の ...
5月26日 08:16 投稿
KMPアルゴリズムによる高速文字列検索
文字列検索問題は、与えられたテキスト文字列 S の中にパターン文字列 P が出現する位置をすべて求める課題である。ナイーブな実装では、各位置から一致を確認し、最悪計算量は O(|S| \cdot |P|) となる。
これを効率化するために、KMP（Knuth-Morris-Pratt）アルゴリズムが用いられる。このアルゴリズムは、マッチング失敗時に無駄な比較を省略することで、線形時間 O(|S ...
5月20日 08:15 投稿