algorithm
サブストリング検索
サーチ…
C言語におけるKMPアルゴリズム
テキストtxtとパターンpatが与えられた場合、このプログラムの目的は、 patのすべての出現をtxtで表示することです。
例：
入力：
txt[] = "THIS IS A TEST TEXT"
pat[] = "TEST"
出力：
Pattern found at index 10
入力：
txt[] = "AABAACAADAABAAABAA"
pat[] = "AABA"
出力：
Pattern found at index 0
Pattern found at index 9
Pattern found at index 13
C言語の実装：
// C program for implementation of KMP pattern searching
// algorithm
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void computeLPSArray(char *pat, int M, int *lps);
void KMPSearch(char *pat, char *txt)
{
int M = strlen(pat);
int N = strlen(txt);
// create lps[] that will hold the longest prefix suffix
// values for pattern
int *lps = (int *)malloc(sizeof(int)*M);
int j = 0; // index for pat[]
// Preprocess the pattern (calculate lps[] array)
computeLPSArray(pat, M, lps);
int i = 0; // index for txt[]
while (i < N)
{
if (pat[j] == txt[i])
{
j++;
i++;
}
if (j == M)
{
printf("Found pattern at index %d \n", i-j);
j = lps[j-1];
}
// mismatch after j matches
else if (i < N && pat[j] != txt[i])
{
// Do not match lps[0..lps[j-1]] characters,
// they will match anyway
if (j != 0)
j = lps[j-1];
else
i = i+1;
}
}
free(lps); // to avoid memory leak
}
void computeLPSArray(char *pat, int M, int *lps)
{
int len = 0; // length of the previous longest prefix suffix
int i;
lps[0] = 0; // lps[0] is always 0
i = 1;
// the loop calculates lps[i] for i = 1 to M-1
while (i < M)
{
if (pat[i] == pat[len])
{
len++;
lps[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
if (len != 0)
{
// This is tricky. Consider the example
// AAACAAAA and i = 7.
len = lps[len-1];
// Also, note that we do not increment i here
}
else // if (len == 0)
{
lps[i] = 0;
i++;
}
}
}
}
// Driver program to test above function
int main()
{
char *txt = "ABABDABACDABABCABAB";
char *pat = "ABABCABAB";
KMPSearch(pat, txt);
return 0;
}
出力：
Found pattern at index 10
参照：
http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/
Rabin-Karpアルゴリズムの紹介
Rabin-Karpアルゴリズムは、 Richard M. KarpとMichael O. Rabinによって作成された文字列検索アルゴリズムで、ハッシュを使用してテキスト内のパターン文字列のいずれかを検索します。
文字列の部分文字列は、別の文字列です。たとえば、 verはstackoverflowの部分文字列です。 カバーは同じ文字列のサブシーケンスであるため、サブシーケンスと混同しないでください。つまり、文字列内の連続する文字のサブセットは、指定された文字列の部分文字列です。
Rabin-Karpアルゴリズムでは、探しているパターンのハッシュを生成し、 テキストのローリングハッシュがパターンと一致するかどうかをチェックします 。一致しない場合は、そのパターン が テキストに 存在しないことが保証されます 。ただし、一致する場合は、 パターン が テキストに存在する可能性があります 。例を見てみましょう：
テキストがあるとしましょう： yeminsajidと、テキストにパターンnsaが存在するかどうかを調べたいとします。ハッシュとローリングハッシュを計算するには、素数を使用する必要があります。これは任意の素数にすることができます。この例では、 prime = 11を取ってみましょう。この式を使用してハッシュ値を決定します。
(1st letter) X (prime) + (2nd letter) X (prime)¹ + (3rd letter) X (prime)² X + ......
我々は以下を示す：
a -> 1 g -> 7 m -> 13 s -> 19 y -> 25
b -> 2 h -> 8 n -> 14 t -> 20 z -> 26
c -> 3 i -> 9 o -> 15 u -> 21
d -> 4 j -> 10 p -> 16 v -> 22
e -> 5 k -> 11 q -> 17 w -> 23
f -> 6 l -> 12 r -> 18 x -> 24
nsaのハッシュ値は次のようになります。
14 X 11⁰ + 19 X 11¹ + 1 X 11² = 344
今度は、テキストのローリングハッシュを見つけます。ローリングハッシュがパターンのハッシュ値と一致する場合、文字列が一致するかどうかを確認します。私たちのパターンは3文字であるので、テキストから最初の3文字のyemを取り 、ハッシュ値を計算します。我々が得る：
25 X 11⁰ + 5 X 11¹ + 13 X 11² = 1653
この値はパターンのハッシュ値と一致しません。したがって、文字列はここには存在しません。今度は次のステップを検討する必要があります。次の文字列emiのハッシュ値を計算する。この計算式を使って計算できます。しかし、それはややこしいことであり、私たちにはより多くの費用がかかります。代わりに、別の手法を使用します。
- 私たちは現在のハッシュ値から前の文字列の最初の文字の値を減算します。この場合、 y 。我々は、
1653 - 25 = 1628を得る。 - この差を、この例では11である素数で割っています。我々は、
1628 / 11 = 148を得る。 - 新しい文字X（素数）ᵐ-1を追加します 。ここで、 mはパターンの長さで、商はi = 9です。
148 + 9 X 11² = 1237ます。
新しいハッシュ値はパターンハッシュ値と等しくありません。私が得るnのために移動する：
Previous String: emi
First Letter of Previous String: e(5)
New Letter: n(14)
New String: "min"
1237 - 5 = 1232
1232 / 11 = 112
112 + 14 X 11² = 1806
それは一致しません。その後、 sについては次のようになります。
Previous String: min
First Letter of Previous String: m(13)
New Letter: s(19)
New String: "ins"
1806 - 13 = 1793
1793 / 11 = 163
163 + 19 X 11² = 2462
それは一致しません。次に、 aについては 、次のようになります。
Previous String: ins
First Letter of Previous String: i(9)
New Letter: a(1)
New String: "nsa"
2462 - 9 = 2453
2453 / 11 = 223
223 + 1 X 11² = 344
それはマッチです！今度はパターンを現在の文字列と比較します。両方の文字列が一致するため、この文字列に部分文字列が存在します。そして、部分文字列の開始位置を返します。
疑似コードは次のようになります。
ハッシュ計算：
Procedure Calculate-Hash(String, Prime, x):
hash := 0 // Here x denotes the length to be considered
for m from 1 to x // to find the hash value
hash := hash + (Value of String[m])ᵐ⁻¹
end for
Return hash
ハッシュ再計算：
Procedure Recalculate-Hash(String, Curr, Prime, Hash):
Hash := Hash - Value of String[Curr] //here Curr denotes First Letter of Previous String
Hash := Hash / Prime
m := String.length
New := Curr + m - 1
Hash := Hash + (Value of String[New])ᵐ⁻¹
Return Hash
文字列一致：
Procedure String-Match(Text, Pattern, m):
for i from m to Pattern-length + m - 1
if Text[i] is not equal to Pattern[i]
Return false
end if
end for
Return true
ラビン=カルプ：
Procedure Rabin-Karp(Text, Pattern, Prime):
m := Pattern.Length
HashValue := Calculate-Hash(Pattern, Prime, m)
CurrValue := Calculate-Hash(Pattern, Prime, m)
for i from 1 to Text.length - m
if HashValue == CurrValue and String-Match(Text, Pattern, i) is true
Return i
end if
CurrValue := Recalculate-Hash(String, i+1, Prime, CurrValue)
end for
Return -1
アルゴリズムで一致するものが見つからない場合は、単に-1を返します。
このアルゴリズムは、盗作の検出に使用されます。与えられたソースマテリアルでは、アルゴリズムは、ケースや句読点などの詳細を無視して、ソースマテリアルからのセンテンスのインスタンスを紙を通して迅速に検索できます。検索文字列が豊富であるため、ここでは単一文字列検索アルゴリズムは実用的ではありません。 Knuth-Morris-PrattアルゴリズムやBoyer-Moore String Searchアルゴリズムは、 Rabin-Karpよりも高速な単一パターン文字列検索アルゴリズムです。しかし、それは複数のパターン検索のための選択アルゴリズムです。テキスト中に多数のk個の固定長パターンを見つけるには、Rabin-Karpアルゴリズムの単純な変形を作成することができます。
長さnのテキストと結合された長さmの p個のパターンの平均および最良の場合の実行時間は、空間O（p）においてO（n + m）であるが、その最悪ケース時間はO（nm）である 。
Knuth-Morris-Pratt（KMP）アルゴリズムの紹介
テキストとパターンがあるとします 。そのパターンがテキストに存在するかどうかを判断する必要があります。例えば：
+-------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+---+---+---+---+---+---+---+---+
| Text | a | b | c | b | c | g | l | x |
+-------+---+---+---+---+---+---+---+---+
+---------+---+---+---+---+
| Index | 0 | 1 | 2 | 3 |
+---------+---+---+---+---+
| Pattern | b | c | g | l |
+---------+---+---+---+---+
このパターンはテキストに存在します 。したがって、部分文字列検索では、このパターンの開始位置のインデックスである3が返されます。だから、私たちの無差別な部分文字列検索手続きはどのように機能しますか？
私たちが通常行うことは、 テキストの0番目のインデックスとパターンの0番目のインデックスから始まり、 Text [0]とPattern [0]を比較します。一致しないので、 テキストの次のインデックスに進み、 Text [1]とPattern [0]を比較します 。これは一致するので、 パターンのインデックスとテキストのインデックスもインクリメントします。 Text [2]とPattern [1]を比較します。彼らはまたマッチです。前述の同じ手順に従って、 テキスト[3]とパターン[2]を比較します。彼らが一致しないので、我々は試合を見つけるのを開始した次の位置からスタートします。それはテキストのインデックス2です。 Text [2]とPattern [0]を比較します。彼らは一致しません。 Textのインデックスをインクリメントして、 Text [3]とPattern [0]を比較します。彼らは一致します。 Text [4]とPattern [1]が一致し、 Text [5]とPattern [2]が一致し、 Text [6]とPattern [3]が一致します。 パターンの終わりに達したので、今度は試合開始のインデックス、つまり3を返します。私たちのパターンが： bcgllだった場合、そのパターンがテキストに存在しなかった場合、検索は例外または-1または他の事前定義された値を返さなければなりません。最悪の場合、このアルゴリズムは、 テキストの長さをm 、 パターンの長さをnとすると、 O(mn)時間かかることがわかります。この時間の複雑さをどのように減らすか？ここにKMPサブストリング検索アルゴリズムが入ります。
Knuth-Morris-Pratt文字列検索アルゴリズムまたはKMPアルゴリズムは、不一致が発生した場合、単語自体が次の一致が始まる場所を決定するのに十分な情報を具体化するという観察を使用して、主な「テキスト」内の「パターン」の出現を検索する以前に一致した文字の再検査をバイパスします。このアルゴリズムは、1970年にDonuld KnuthとVaughan Prattによって、そして独立してJames H. Morrisによって考案されました。このトリオは1977年に共同で出版した。
のは、より良く理解するために私たちの例のテキストとパターンを拡張してみましょう：
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| Index |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|13|14|15|16|17|18|19|20|21|22|
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| Text |a |b |c |x |a |b |c |d |a |b |x |a |b |c |d |a |b |c |d |a |b |c |y |
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | y |
+---------+---+---+---+---+---+---+---+---+
最初は、 テキストとパターンがインデックス2まで一致します。 テキスト[3]とパターン[3]が一致しません。ですから、私たちの目標は、このテキストで後ろ向きにしないことです。つまり、不一致の場合、マッチングを開始する位置から再びマッチングを開始することはありません。これを達成するために、不一致が発生する前にパターンの サフィックスを探します（サブストリングabc ）。 パターンの部分文字列の接頭辞でもあります 。この例では、すべての文字が一意であるため、一致する部分文字列の接頭辞である接尾辞はありません。つまり、次の比較はインデックス0から始まります。ちょっと待って、なぜこれをやったのか理解できます。次に、 Text [3]とPattern [0]を比較し、一致しません。その後、インデックス4からインデックス9までのテキストに対して、インデックス0からインデックス5までのパターンに対して、一致するものが見つかる。 テキスト[10]とパターン[6]には不一致があります。したがって、不一致が発生するポイント（サブストリングabcdabc ）の直前のパターンからサブストリングを取ります。このサブストリングの接頭部でもある接尾辞を調べます。ここで、 abはこの部分文字列の接尾辞と接頭辞の両方です。つまり、 テキスト[10]までマッチしているので、不一致の直前の文字はabです。私たちが推測できるのは、 abもまた部分文字列の接頭辞であるため、 abを再度チェックする必要はなく、次のチェックはText [10]とPattern [2]から始めることができます。 テキスト全体を振り返る必要はなく、不一致が発生した場所から直接開始することができます。文字列[10]とパターン[2]は不一致であり、不一致の前の部分文字列（ abc ）に接頭辞でもある接尾辞が含まれていないので、 テキスト[10]とパターン[0]をチェックします 。彼らは一致しません。その後、インデックス11からインデックス17までのテキストと、インデックス0からインデックス6までのパターンの テキスト 。 テキスト[18]とパターン[7]には不一致があります。もう一度、一致しない部分文字列（部分文字列abcdabc ）を調べ、 abcが接尾辞と接頭辞の両方であることを確認します。 パターン[7]まで一致して以来、 abcはText [18]より前でなければなりません。つまり、 Text [17]まで比較する必要はなく、 Text [18]とPattern [3]から比較を開始します。したがって、我々は試合を見つけるだろうし、試合の開始点である15を返す。これは、KMP Substring Searchが接尾辞と接頭辞情報を使用して動作する方法です。
ここで、接尾辞が接頭辞と同じであるか、 テキストとパターンの間に文字の不一致がある場合、どの点でチェックを開始するかを効率的に計算する方法を説明します。例を見てみましょう：
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
必要な情報を含む配列を生成します。配列Sを呼び出しましょう。配列のサイズは、パターンの長さと同じになります。 パターンの最初の文字は接頭辞の接尾辞にはなりませんので、 S [0] = 0とします。最初はi = 1 、 j = 0とする。各ステップで、 Pattern [i]とPattern [j]を比較し、 iをインクリメントします。もし一致があれば、 S [i] = j + 1をインクリメントしてjをインクリメントし、もし不一致があれば、 jの以前の値の位置をチェックし、 j = S [j-1] （ jが0に等しくない場合）、 S [j]がS [i]と一致しないかjが0にならなくなるまでこれを続けます 。後者の場合、 S [i] = 0とする 。私たちの例では：
j i
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
Pattern [j]とPattern [i]は一致しないので、 iをインクリメントし、 jは0なので 、前の値をチェックせずにPattern [i] = 0とします。我々はI = 4のために、 私をインクリメントし続けるならば、我々は試合を取得しますので、我々は[i]は =のS [4] = J + 1 = 0 + 1 = 1とインクリメントjとI Sを置きます。私たちの配列は次のようになります：
j i
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
| S | 0 | 0 | 0 | 0 | 1 | | | |
+---------+---+---+---+---+---+---+---+---+
Pattern [1]とPattern [5]は一致するので、 S [i] = S [5] = j + 1 = 1 + 1 = 2とする 。続ければ、 j = 3とi = 7の不一致が見つかるでしょう。 jは0に等しくないので、 j = S [j-1]とする 。そして私たちは、 iとjの文字を同じかどうか比較します。同じであるかどうかは同じですから、 S [i] = j + 1とします。完成した配列は次のようになります：
+---------+---+---+---+---+---+---+---+---+
| S | 0 | 0 | 0 | 0 | 1 | 2 | 3 | 1 |
+---------+---+---+---+---+---+---+---+---+
これは私たちの必要な配列です。ここでS [I]の非ゼロ値は、Sの[i]が + 1つの位置から開始され、そのサブストリング（iを0からサブストリング）でプレフィックスと次の比較と同様S [i]の長さのサフィックスが存在することを意味しますパターン 。配列を生成するアルゴリズムは次のようになります。
Procedure GenerateSuffixArray(Pattern):
i := 1
j := 0
n := Pattern.length
while i is less than n
if Pattern[i] is equal to Pattern[j]
S[i] := j + 1
j := j + 1
i := i + 1
else
if j is not equal to 0
j := S[j-1]
else
S[i] := 0
i := i + 1
end if
end if
end while
この配列を構築する時間の複雑さはO(n)あり、空間の複雑さもO(n) 。アルゴリズムを完全に理解しているかどうかを確認するには、パターンaabaabaa配列を生成し、結果がこのパターンと一致するかどうかを確認してください。
次に、次の例を使って部分文字列検索をしましょう：
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
| Text | a | b | x | a | b | c | a | b | c | a | b | y |
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
+---------+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 |
+---------+---+---+---+---+---+---+
| Pattern | a | b | c | a | b | y |
+---------+---+---+---+---+---+---+
| S | 0 | 0 | 0 | 1 | 2 | 0 |
+---------+---+---+---+---+---+---+
これまでに定義したロジックを使用して、 テキスト 、 パターン 、事前に計算された配列Sがあります。 Text [0]とPattern [0]を比較して同じです。 テキスト[1]とパターン[1]は同じです。 テキスト[2]とパターン[2]は同じではありません。不一致の直前の位置の値をチェックします。 S [1]は0なので 、私たちの部分文字列の接頭辞と同じ接尾辞はなく、比較は位置S [1]から始まります 。これは0です。だからパターン[0]はテキスト[2]と同じではありません。 Text [3]はPattern [0]と同じで、 Text [8]とPattern [5]まで一致します。私たちはS配列で一歩一歩進み、 2を見つけます。つまり、この部分文字列（ abcab）の接尾辞でもある長さ2の接頭辞がabであることを意味します。つまり、 テキスト[8]の前にabがあることを意味します。ですから、 パターン[0]とパターン[1]を無視し、 パターン[2]とテキスト[8]から次の比較を開始することができます。私たちが続けるならば、私たちはテキストの パターンを見つけるでしょう。私たちの手順は次のようになります：
Procedure KMP(Text, Pattern)
GenerateSuffixArray(Pattern)
m := Text.Length
n := Pattern.Length
i := 0
j := 0
while i is less than m
if Pattern[j] is equal to Text[i]
j := j + 1
i := i + 1
if j is equal to n
Return (j-i)
else if i < m and Pattern[j] is not equal t Text[i]
if j is not equal to 0
j = S[j-1]
else
i := i + 1
end if
end if
end while
Return -1
サフィックス配列計算とは別に、このアルゴリズムの時間複雑度はO(m)です。 GenerateSuffixArrayはO(n) を取るので、KMPアルゴリズムの総時間複雑度はO(m+n)です。
PS： TextでPatternを複数見つけたい場合は、値を返す代わりにprint / storeし、 j := S[j-1]ます。また、発生を検出したかどうかを追跡するflagを保持し、それに応じて処理します。
KMPアルゴリズムのPython実装。
Haystack ：指定されたパターンを検索する必要がある文字列。
Needle ：検索するパターン。
時間計算 ：検索部（はstrstr法）複雑性O（N）はn干し草の山の長さがなく、針はまたプレフィックステーブルO（m）を構築するために解析さプレ通りであるプリフィックス・テーブルを構築するために必要とされるmの長さであります針。
したがって、KMPの全体的な時間複雑度はO（n + m）
空間の複雑さ ： O（m）針の接頭語テーブルのために。
注意：実装の後、haystackでの一致の開始位置が返されます（一致する場合）。それ以外の場合は、needle / haystackが空文字列か針がhaystackに見つからない場合などに-1が返されます。
def get_prefix_table(needle):
prefix_set = set()
n = len(needle)
prefix_table = [0]*n
delimeter = 1
while(delimeter<n):
prefix_set.add(needle[:delimeter])
j = 1
while(j<delimeter+1):
if needle[j:delimeter+1] in prefix_set:
prefix_table[delimeter] = delimeter - j + 1
break
j += 1
delimeter += 1
return prefix_table
def strstr(haystack, needle):
# m: denoting the position within S where the prospective match for W begins
# i: denoting the index of the currently considered character in W.
haystack_len = len(haystack)
needle_len = len(needle)
if (needle_len > haystack_len) or (not haystack_len) or (not needle_len):
return -1
prefix_table = get_prefix_table(needle)
m = i = 0
while((i<needle_len) and (m<haystack_len)):
if haystack[m] == needle[i]:
i += 1
m += 1
else:
if i != 0:
i = prefix_table[i-1]
else:
m += 1
if i==needle_len and haystack[m-1] == needle[i-1]:
return m - needle_len
else:
return -1
if __name__ == '__main__':
needle = 'abcaby'
haystack = 'abxabcabcaby'
print strstr(haystack, needle)
