Oの文字列内のサブストリングの発生回数（N）

Question

Iは線形時間で干し草の山の中の各針の出現箇所の数をカウントする方法を思っていました。私はAho-Corasickのアルゴリズムを使うと思っていたが、私は時間の複雑さを針の発生回数に依存させたくなかった。あなたは、文字列のセットを検索したい発生数に依存して好きではない場合

Answer 1

はRabin–Karpを使用してください。実行時間、平均/最高の場合はO(n + m)であるが、その最悪の場合の時間がnテキストとmの長さであり、O（nm）は、検索パターンの組み合わせた長さです。

あなたはnは、テキストの長さであり、kは、検索パターンの長さで複雑O(n + k)、とKnuth–Morris–Prattを使用することができる唯一の1つの文字列を検索したい場合は。

Answer 2

合計発生回数だけ必要な場合（また、位置自体は気にしない場合）、Aho-Corasickを効率的に使用できます。現在、ノードvにいるとします。現在の位置で終了する部分文字列の数。私はそれが正確に接尾辞リンクによってvから到達可能なターミナルノードの数だと主張しています。しかし、サフィックスリンクはツリーを形成します。したがって、接尾辞リンクによって形成されるツリー内のルート上の末尾頂点の数をvから数える必要があります。線形前処理（例えば、このツリーを明示的に構築し、深度優先探索を使用して、直線から任意の頂点へのパス上の合計を線形時間で計算することができます）で時間を計算することができます（O(1)）。我々はまた、（例えば、高さの昇順で）正しい順序で頂点を処理し、sum[v] += sum[suffix_link(v)]ような何かを行うことができます。その場合、実際にこのツリーを構築する必要はありません。

このアルゴリズムは、Aho-Corasickオートマトンを構築し、線形時間で「サフィックスリンクパス」の合計を計算し、通常のようにオートマトンを使用することで、 。