行の検索問題のステートメント
多くの場合、特定の検索、いわゆる文字列検索（文字列での検索）を処理する必要があります。 テキストTと単語（または画像）Wがあるとします。指定されたテキストでこの単語の最初の出現を見つける必要があります。 このアクションは、あらゆるワードプロセッシングシステムで一般的なものです。 （配列TとWの要素は、有限のアルファベットの記号です。たとえば、{0、1}、または{a、...、z}、または{a、...、i}。）
このようなタスクの最も典型的なアプリケーションは、ドキュメンタリー検索です。書誌参照のシーケンスからなるドキュメントのコレクションが提供され、各リンクには、対応するリンクの主題を示す「記述子」が付随します。 記述子の中にあるキーワードを見つける必要があります。 たとえば、「プログラミング」と「Java」のリクエストです。 このようなリクエストは、次のように解釈できます。記述子「Programming」および「Java」を持つ記事はありますか。
文字列検索は、次のように正式に定義されています。 N個の要素の配列TとM個の要素の配列Wが与えられ、0 <M≤Nであるとします。 文字列検索は、TでのWの最初の出現を検出します。結果はインデックスiで、行の先頭（配列Tの先頭）から画像（単語）との最初の一致を示します。
例。 テキストT = abcabaabcabca内のパターンW = abaaのすべての出現箇所を見つける必要があります。
サンプルは、S = 3、インデックスi = 4のシフトで1回だけテキストに含まれます。
直接検索アルゴリズム
アルゴリズムのアイデア：
1. I = 1
2.配列TのI番目の文字を配列Wの最初の文字と比較します。
3.一致→2番目の文字を比較するなど。
4.不一致→I：= I + 1、ポイント2に移動
アルゴリズムの終了条件：
1. M行の比較が成功した場合、
2. I + M> N、つまり、単語が見つかりませんでした。
アルゴリズムの複雑さ：
最悪の場合。 配列T→{AAA ... .AAAB}、長さ│T│= N、サンプルW→{A ... .AB}、長さ│W│= Mとしましょう。 明らかに、行の終わりで一致を見つけるには、N * M比較の順序、つまりO（N * M）を作成する必要があります。
アルゴリズムの欠点：
1.高度な複雑性-O（N * M）、最悪の場合-Θ（（N-M + 1）* M）;
2.不一致の後、表示は常にサンプルの最初の文字から始まるため、以前に表示されたT文字が含まれる場合があります（文字列がセカンダリメモリから読み取られる場合、このような戻りには多くの時間がかかります）。
3.このシフトSをチェックすることによって取得されたテキストTについての情報は、後続のシフトをチェックするときに使用されません。
D.クヌース、D。モーリス、V。プラットのアルゴリズム（KMP-search）
KMP検索アルゴリズムでは、実際には最悪の場合でもN次の比較のみが必要です。
例。
（比較された文字には下線が引かれています。）
画像Wの最初の部分が文字列Tの対応する文字と部分的に一致した後、文字列の渡された部分を実際に知り、（Wの画像に基づいて）いくつかの情報を「計算」できます。
KMP検索の考え方は、テキストと画像の2つの文字が一致しない場合、移動距離全体で画像がシフトすることです。小さなシフトでは完全に一致することはできないためです。
KMP検索の機能：
1.結果を取得するには、（N + M）文字の比較が必要です。
2. KMP検索スキームは、特定の数の一致が障害の前に発生した場合にのみ、実際のゲインを提供します。 この場合にのみ、画像が複数シフトします。 残念ながら、偶然の一致は不一致よりもはるかに少ないです。 したがって、テキストのほとんどの場合のKMP検索からの利益は非常にわずかです。
R. BowerおよびD. Mooreのアルゴリズム（BM検索）
実際には、パターンWが長く、アルファベットのパワーが十分に大きい場合、BM検索アルゴリズムが最も効果的です。
BM検索の考え方は、文字の比較はパターンの最後から始まり、最初からではないということです。つまり、個々の文字の比較は右から左に行われます。 次に、特定のヒューリスティック手順を使用して、右へのシフトsが計算されます。 繰り返しますが、文字はパターンの最後から比較されます。
この方法は、最悪の場合の処理を改善するだけでなく、中間の状況でも勝利をもたらします。
ほとんどの場合、特別に作成された例を除き、BM検索はN比較を大幅に少なくします。 最も好ましい状況では、サンプルの最後の文字が常にテキストの不一致文字に該当する場合、比較の数は（N / M）、最悪の場合はO（（N-M + 1）* M + p）、pはアルファベットの累乗です。
Rabin-Karpアルゴリズム（RK-search）
アルファベットをD = {0、1、2、3、4、5、6、7、8、9}とします。つまり、アルファベットの各文字はd – 10進数で、d =│D│です。
例。 サンプルの形式をW = 3 1 4 1 5とする
mod qで長さ| W | = 5のウィンドウから数値の値を計算します。qは素数です。
23590（mod 13）= 8、35902（mod 13）= 9、59023（mod 13）= 9、...
k1 =314157（mod 13）-サンプルのエントリ、
k2 =673997（mod 13）-アイドル操作。
等式ki = kj（mod q）からki = kj（たとえば、31515 = 67399（mod 13）にはなりませんが、これは31415 = 67399という意味ではありません）。 ki = kj（mod q）の場合、行W [1 ... m]とT [s + 1 ... s + m]が実際に一致するかどうかを確認する必要があります。
プライムqが十分に大きい場合、アイドル応答を分析するための追加コストは小さくなります。
最悪の場合、RKアルゴリズムの実行時間はΘ（（N-M + 1）* M）であり、平均して、O（N + M）時間中は非常に高速に動作します。
例：RKアルゴリズムが何個の空白kを作成するか
q = 11、13、17. W = {2 6}とする
26 mod 11 = 4→k = 3回のアイドルトリップ、
26 mod 13 = 0→k = 1アイドル、
26 mod 17 = 9→k = 0アイドル時間。
明らかに、空白の数kは素数qの関数（サンプル処理関数がmod qの場合）であり、一般的な場合、サンプルWとテキストTを処理するための関数のタイプです。