algorithm
Wyszukiwanie podciągów
Szukaj…
Algorytm KMP w C
Biorąc pod uwagę txt tekst i pat wzór, celem tego programu będzie drukować wszystkie występowaniu gazów pat w txt.
Przykłady:
Wejście:
txt[] = "THIS IS A TEST TEXT"
pat[] = "TEST"
wynik:
Pattern found at index 10
Wejście:
txt[] = "AABAACAADAABAAABAA"
pat[] = "AABA"
wynik:
Pattern found at index 0
Pattern found at index 9
Pattern found at index 13
Implementacja języka 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;
}
Wynik:
Found pattern at index 10
Odniesienie:
http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-alameterm/
Wprowadzenie do algorytmu Rabin-Karp
Algorytm Rabin-Karp jest algorytmem wyszukiwania ciągów stworzonym przez Richarda M. Karpa i Michaela O. Rabin, który używa haszowania do znalezienia dowolnego zestawu ciągów znaków w tekście.
Podciąg ciągu to kolejny ciąg, który występuje w. Na przykład ver jest podciągiem przepływu stosu . Nie należy mylić z podsekwencją, ponieważ cover jest podsekwencją tego samego łańcucha. Innymi słowy, dowolny podzbiór kolejnych liter w ciągu znaków jest podciągiem danego ciągu.
W algorytmie Rabin-Karp wygenerujemy skrót naszego wzoru , którego szukamy, i sprawdzimy, czy zmienny skrót naszego tekstu pasuje do wzorca, czy nie. Jeśli nie pasuje, możemy zagwarantować, że wzór nie istnieje w tekście . Jeśli jednak pasuje, wzór może być obecny w tekście . Spójrzmy na przykład:
Powiedzmy, że mamy tekst: yeminsajid i chcemy dowiedzieć się, czy wzorzec nsa istnieje w tekście. Aby obliczyć skrót i kroczący skrót, będziemy musieli użyć liczby pierwszej. Może to być dowolna liczba pierwsza. Weźmy liczbę pierwszą = 11 dla tego przykładu. Wartość skrótu określimy za pomocą tej formuły:
(1st letter) X (prime) + (2nd letter) X (prime)¹ + (3rd letter) X (prime)² X + ......
Oznaczymy:
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
Wartość skrótu nsa będzie wynosić:
14 X 11⁰ + 19 X 11¹ + 1 X 11² = 344
Teraz znajdujemy skrót naszego tekstu. Jeśli kroczący skrót pasuje do wartości skrótu naszego wzorca, sprawdzimy, czy ciągi pasują, czy nie. Ponieważ nasz wzór ma 3 litery, weźmiemy 1–3 litery z naszego tekstu i obliczymy wartość skrótu. Otrzymujemy:
25 X 11⁰ + 5 X 11¹ + 13 X 11² = 1653
Ta wartość nie zgadza się z wartością skrótu naszego wzorca. Więc ciąg nie istnieje tutaj. Teraz musimy rozważyć następny krok. Aby obliczyć wartość skrótu naszego następnego emi ciągu. Możemy to obliczyć za pomocą naszego wzoru. Ale byłoby to raczej banalne i kosztowało nas więcej. Zamiast tego używamy innej techniki.
- Odejmujemy wartość pierwszej litery poprzedniego ciągu od naszej bieżącej wartości skrótu. W tym przypadku y . Otrzymujemy
1653 - 25 = 1628. - Różnicę dzielimy na liczbę pierwszą , która w tym przykładzie wynosi 11 . Otrzymujemy
1628 / 11 = 148. - Dodajemy nową literę X (pierwsza) ᵐ⁻¹ , gdzie m jest długością wzoru, z ilorazem, który wynosi i = 9 . Otrzymujemy
148 + 9 X 11² = 1237.
Nowa wartość skrótu nie jest równa wartości skrótu naszych wzorów. Idąc dalej, za n otrzymujemy:
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
To nie pasuje. Następnie, dla s , otrzymujemy:
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
To nie pasuje. Następnie, dla, otrzymujemy:
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
To pasuje! Teraz porównujemy nasz wzór z bieżącym ciągiem. Ponieważ oba ciągi pasują do siebie, w tym ciągu istnieje podciąg. I zwracamy pozycję początkową naszego podciągu.
Pseudo-kod będzie:
Obliczanie skrótu:
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
Ponowne obliczenie skrótu:
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
Ciąg pasujący:
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
Rabin-Karp:
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
Jeśli algorytm nie znajdzie żadnego dopasowania, po prostu zwraca -1 .
Algorytm ten wykorzystywany jest w wykrywaniu plagiatu. Biorąc pod uwagę materiał źródłowy, algorytm może szybko przeszukiwać papier w poszukiwaniu wystąpień zdań z materiału źródłowego, ignorując takie szczegóły, jak wielkość liter i interpunkcja. Ze względu na dużą liczbę poszukiwanych ciągów algorytmy przeszukiwania pojedynczych ciągów są tutaj niepraktyczne. Ponownie, algorytm Knuth-Morris-Pratt lub algorytm Boyer-Moore String Search jest szybszym algorytmem wyszukiwania ciągu pojedynczego wzorca, niż Rabin-Karp . Jest to jednak algorytm z wyboru do wyszukiwania wielu wzorów. Jeśli chcemy znaleźć dowolną dużą liczbę, powiedzmy k, wzory o stałej długości w tekście, możemy stworzyć prosty wariant algorytmu Rabin-Karp.
Dla tekstu o wzorcach długości n i p o łącznej długości m , jego średni i najlepszy czas działania w przypadku O wynosi n (n + m) w przestrzeni O (p) , ale jego najgorszym czasem jest O (nm) .
Wprowadzenie do algorytmu Knuth-Morris-Pratt (KMP)
Załóżmy, że mamy tekst i wzór . Musimy ustalić, czy wzór istnieje w tekście, czy nie. Na przykład:
+-------+---+---+---+---+---+---+---+---+
| 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 |
+---------+---+---+---+---+
Ten wzór istnieje w tekście . Dlatego nasze wyszukiwanie podłańcuchów powinno zwrócić 3 , indeks pozycji, od której zaczyna się ten wzorzec . Jak więc działa procedura wyszukiwania podciągów siłowych?
Zwykle robimy to: zaczynamy od 0 indeksu tekstu i 0 indeksu naszego * wzoru i porównujemy Tekst [0] ze Wzorem [0] . Ponieważ nie pasują do siebie, przechodzimy do następnego indeksu naszego tekstu i porównujemy Tekst [1] ze Wzorem [0] . Ponieważ jest to dopasowanie, zwiększamy również indeks naszego wzorca i indeks tekstu . Porównujemy Tekst [2] ze Wzorem [1] . Są również pasujące. Postępując zgodnie z tą samą procedurą, co poprzednio, porównujemy teraz Tekst [3] ze Wzorem [2] . Ponieważ się nie zgadzają, zaczynamy od następnej pozycji, w której zaczęliśmy znajdować dopasowanie. To jest indeks 2 tekstu . Porównujemy Tekst [2] ze Wzorem [0] . Nie pasują. Następnie zwiększając indeks tekstu , porównujemy tekst [3] ze wzorem [0] . Pasują do siebie. Znów dopasowanie tekstu [4] i wzoru [1], dopasowanie tekstu [5] i wzoru [2] oraz dopasowanie tekstu [6] i wzoru [3] . Ponieważ osiągnęliśmy koniec naszego Wzorca , zwracamy teraz indeks, od którego zaczęło się nasze dopasowanie, czyli 3 . Jeśli nasz wzorzec to: bcgll , oznacza to, że jeśli wzorzec nie istniał w naszym tekście , nasze wyszukiwanie powinno zwrócić wyjątek lub -1 lub dowolną inną predefiniowaną wartość. Widzimy wyraźnie, że w najgorszym przypadku algorytm ten O(mn) czas O(mn) gdzie m jest długością Tekstu, a n jest długością Wzorca . Jak zmniejszyć złożoność czasu? W tym miejscu pojawia się algorytm wyszukiwania podciągów KMP.
Algorytm wyszukiwania ciągów Knutha-Morrisa-Pratta lub algorytm KMP wyszukuje wystąpienia „wzorca” w głównym „tekście”, wykorzystując spostrzeżenie, że w przypadku wystąpienia niezgodności samo słowo zawiera wystarczające informacje, aby określić, gdzie może rozpocząć się następne dopasowanie , pomijając w ten sposób ponowne sprawdzenie wcześniej dopasowanych znaków. Algorytm został opracowany w 1970 roku przez Donulda Knutha i Vaughana Pratta i niezależnie przez Jamesa H. Morrisa . Trio opublikowało go wspólnie w 1977 roku.
Rozszerzmy nasz przykładowy tekst i wzór, aby lepiej zrozumieć:
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 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 |
+---------+---+---+---+---+---+---+---+---+
Na początku nasze Tekst i Wzór pasują do indeksu 2 . Tekst [3] i wzór [3] nie pasują. Dlatego naszym celem jest nie cofanie się w tym tekście , to znaczy, w przypadku niezgodności, nie chcemy, aby nasze dopasowywanie zaczynało się od pozycji, z którą zaczęliśmy dopasowywać. Aby to osiągnąć, szukamy sufiksu w naszym Wzorze tuż przed wystąpieniem naszego niedopasowania (substring abc ), który jest również przedrostkiem podłańcucha naszego Wzorca . W naszym przykładzie, ponieważ wszystkie znaki są unikalne, nie ma przyrostka, który jest przedrostkiem naszego dopasowanego podłańcucha. Oznacza to, że nasze następne porównanie rozpocznie się od indeksu 0 . Poczekaj chwilę, zrozumiesz, dlaczego to zrobiliśmy. Następnie porównujemy Tekst [3] ze Wzorem [0] i nie pasuje. Następnie dla tekstu od indeksu 4 do indeksu 9 i wzoru od indeksu 0 do indeksu 5 znajdujemy dopasowanie. Niedopasowanie znajdujemy w tekście [10] i wzorze [6] . Tak więc bierzemy podłańcuch ze Wzorca tuż przed punktem, w którym występuje niezgodność (podciąg abcdabc ), sprawdzamy przyrostek, który jest także przedrostkiem tego podłańcucha. Widzimy tutaj, że ab jest zarówno przyrostkiem, jak i przedrostkiem tego podłańcucha. Oznacza to, że ponieważ dopasowaliśmy do tekstu [10] , znaki tuż przed niezgodnością to ab . Możemy z tego wywnioskować, że ponieważ ab jest także przedrostkiem podciągniętego podciągnięcia, nie musimy sprawdzać ab ponownie, a następne sprawdzanie może rozpocząć się od Tekstu [10] i Wzorca [2] . Nie musieliśmy patrzeć wstecz na cały tekst , możemy zacząć bezpośrednio od miejsca, w którym nastąpiło nasze niedopasowanie. Teraz sprawdzamy Tekst [10] i Wzorzec [2] , ponieważ jest to niezgodność, a podłańcuch przed niezgodnością ( abc ) nie zawiera sufiksu, który jest również przedrostkiem, sprawdzamy Tekst [10] i Wzorzec [0] , nie pasują. Następnie dla tekstu od indeksu 11 do indeksu 17 i wzoru od indeksu 0 do indeksu 6 . Niedopasowanie znajdujemy w tekście [18] i wzorze [7] . Ponownie sprawdzamy podłańcuch przed niezgodnością (podciąg abcdabc ) i znajdujemy, że abc jest zarówno przyrostkiem, jak i przedrostkiem. Skoro więc dopasowaliśmy do wzoru [7] , abc musi znajdować się przed tekstem [18] . Oznacza to, że nie musimy porównywać do czasu Tekstu [17], a nasze porównanie rozpocznie się od Tekstu [18] i Wzorca [3] . Tak więc znajdziemy dopasowanie i zwrócimy 15, co jest naszym początkowym indeksem dopasowania. Tak działa nasze wyszukiwanie podciągów KMP przy użyciu informacji o sufiksie i prefiksie.
W jaki sposób wydajnie obliczamy, czy przyrostek jest taki sam jak przedrostek, i w którym momencie rozpocząć sprawdzanie, czy występuje niezgodność znaków między tekstem a wzorcem . Spójrzmy na przykład:
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
Wygenerujemy tablicę zawierającą wymagane informacje. Nazwijmy tablicę S. Rozmiar tablicy będzie taki sam jak długość wzorca. Ponieważ pierwsza litera Wzorca nie może być sufiksem żadnego prefiksu, wstawimy S [0] = 0 . Najpierw przyjmujemy i = 1 i j = 0 . Na każdym kroku porównujemy Wzór [i] i Wzór [j] i przyrost i . Jeśli istnieje dopasowanie, wstawiamy S [i] = j + 1 i zwiększamy j , jeśli występuje niezgodność, sprawdzamy pozycję poprzedniej wartości j (jeśli jest dostępna) i ustawiamy j = S [j-1] (jeśli j nie jest równe 0 ), robimy to, dopóki S [j] nie będzie pasować do S [i] lub j nie stanie się 0 . W późniejszym przypadku wstawiamy S [i] = 0 . W naszym przykładzie:
j i
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
Wzorzec [j] i Wzorzec [i] nie pasują, więc zwiększamy i, a ponieważ j wynosi 0 , nie sprawdzamy poprzedniej wartości i nie umieszczamy Wzorca [i] = 0 . Jeśli będziemy dalej zwiększać i , dla i = 4 , otrzymamy dopasowanie, więc wstawiamy S [i] = S [4] = j + 1 = 0 + 1 = 1 i zwiększamy j i i . Nasza tablica będzie wyglądać następująco:
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 | | | |
+---------+---+---+---+---+---+---+---+---+
Ponieważ wzorzec [1] i wzorzec [5] są zgodne, wstawiamy S [i] = S [5] = j + 1 = 1 + 1 = 2 . Jeśli będziemy kontynuować, znajdziemy niedopasowanie dla j = 3 i i = 7 . Ponieważ j nie jest równe 0 , wstawiamy j = S [j-1] . A my porównać znaki z I oraz J są takie same, czy też nie, ponieważ są one takie same, umieścimy S [i] = j + 1. Nasze zakończone tablica będzie wyglądać następująco:
+---------+---+---+---+---+---+---+---+---+
| S | 0 | 0 | 0 | 0 | 1 | 2 | 3 | 1 |
+---------+---+---+---+---+---+---+---+---+
To jest nasza wymagana tablica. Tutaj niezerowa wartość S [i] oznacza, że istnieje sufiks długości S [i] taki sam jak przedrostek w tym podciągu (podciąg od 0 do i ), a następne porównanie rozpocznie się od pozycji S [i] + 1 pozycji Wzór Nasz algorytm do generowania tablicy wyglądałby następująco:
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
Złożoność czasowa budowy tej tablicy wynosi O(n) a złożoność przestrzeni również wynosi O(n) . Aby upewnić się, że całkowicie zrozumiałeś algorytm, spróbuj wygenerować tablicę dla wzoru aabaabaa i sprawdź, czy wynik pasuje do tego .
Teraz wykonajmy wyszukiwanie podciągów, korzystając z następującego przykładu:
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
| 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 |
+---------+---+---+---+---+---+---+
Mamy tekst , wzorzec i wstępnie obliczoną tablicę S, używając naszej wcześniej zdefiniowanej logiki. Porównujemy Tekst [0] i Wzorzec [0] i są one takie same. Tekst [1] i wzór [1] są takie same. Tekst [2] i Wzór [2] nie są takie same. Sprawdzamy wartość w pozycji tuż przed niedopasowaniem. Ponieważ S [1] wynosi 0 , nie ma sufiksu, który byłby taki sam jak przedrostek w naszym podciągu, a nasze porównanie rozpoczyna się od pozycji S [1] , która wynosi 0 . Zatem wzorzec [0] nie jest taki sam jak Tekst [2] , więc przechodzimy dalej. Tekst [3] jest taki sam jak Wzorzec [0] i istnieje zgodność do Tekstu [8] i Wzorca [5] . Cofamy się o krok w tablicy S i znajdujemy 2 . Oznacza to, że istnieje prefiks o długości 2, który jest również sufiksem tego podłańcucha ( abcab), którym jest ab . Oznacza to również, że przed tekstem jest ab [8] . Możemy więc bezpiecznie zignorować wzorzec [0] i wzorzec [1] i rozpocząć nasze następne porównanie od wzorca [2] i tekstu [8] . Jeśli będziemy kontynuować, znajdziemy wzór w tekście . Nasza procedura będzie wyglądać następująco:
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
Złożoność czasowa tego algorytmu oprócz obliczenia tablicy sufiksów wynosi O(m) . Ponieważ GenerateSuffixArray przyjmuje O(n) , całkowity czas złożoności algorytmu KMP wynosi: O(m+n) .
PS: Jeśli chcesz znaleźć wiele wystąpień Wzorca w tekście , zamiast zwracać wartość, wydrukuj ją / zapisz i ustaw j := S[j-1] . Zachowaj także flag aby śledzić, czy znalazłeś jakieś zdarzenie, czy nie i odpowiednio go obsłuż.
Implementacja algorytmu KMP w języku Python.
Stóg siana : ciąg, w którym należy wyszukać dany wzór.
Igła : wzór do przeszukania.
Złożoność czasowa : Część wyszukiwania (metoda strstr) ma złożoność O (n), gdzie n jest długością stogu siana, ale ponieważ igła jest również analizowana do budowania tabeli prefiksów O (m) jest wymagana do budowania tabeli prefiksów, gdzie m jest długością igła.
Dlatego ogólna złożoność czasu dla KMP wynosi O (n + m)
Złożoność przestrzeni : O (m) z powodu tabeli prefiksów na igle.
Uwaga: Po implementacji zwraca pozycję początkową dopasowania w stogu siana (jeśli istnieje dopasowanie), w przeciwnym razie zwraca -1, dla przypadków krawędziowych, np. Jeśli igła / stóg siana jest pustym łańcuchem lub igły nie znaleziono w stogu siana.
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)
