algorithm
Substring zoeken
Zoeken…
KMP-algoritme in C
Gegeven een tekst txt en een patroon pat , is het doel van dit programma om alle exemplaren van pat in txt af te drukken.
Voorbeelden:
Invoer:
txt[] = "THIS IS A TEST TEXT"
pat[] = "TEST"
output:
Pattern found at index 10
Invoer:
txt[] = "AABAACAADAABAAABAA"
pat[] = "AABA"
output:
Pattern found at index 0
Pattern found at index 9
Pattern found at index 13
C Taalimplementatie:
// 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;
}
Output:
Found pattern at index 10
Referentie:
http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/
Inleiding tot het Rabin-Karp-algoritme
Rabin-Karp Algorithm is een tekenreekszoekalgoritme gemaakt door Richard M. Karp en Michael O. Rabin dat hashing gebruikt om een van een set patroonreeksen in een tekst te vinden.
Een substring van een string is een andere string die voorkomt in. Ver is bijvoorbeeld een substring van stackoverflow . Niet te verwarren met subreeks omdat dekking een subreeks van dezelfde reeks is. Met andere woorden, elke subset van opeenvolgende letters in een string is een substring van de gegeven string.
In het Rabin-Karp-algoritme genereren we een hash van ons patroon die we zoeken en controleren we of de hash van onze tekst overeenkomt met het patroon of niet. Als het niet overeenkomt, kunnen we garanderen dat het patroon niet bestaat in de tekst . Echter, als het niet overeenkomt met het patroon kan aanwezig zijn in de tekst vermeld wordt. Laten we een voorbeeld bekijken:
Laten we zeggen dat we een tekst hebben: yeminsajid en we willen weten of het patroon nsa in de tekst voorkomt. Om de hash en de rolling hash te berekenen, moeten we een priemgetal gebruiken. Dit kan elk priemgetal zijn. Laten we voor dit voorbeeld prime = 11 nemen. We bepalen de hash-waarde met behulp van deze formule:
(1st letter) X (prime) + (2nd letter) X (prime)¹ + (3rd letter) X (prime)² X + ......
We geven aan:
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
De hash-waarde van nsa zal zijn:
14 X 11⁰ + 19 X 11¹ + 1 X 11² = 344
Nu vinden we de hash van onze tekst. Als de rollende hash overeenkomt met de hash-waarde van ons patroon, controleren we of de tekenreeksen overeenkomen of niet. Omdat ons patroon 3 letters heeft, nemen we de 1e 3 letters yem uit onze tekst en berekenen we de hash-waarde. We krijgen:
25 X 11⁰ + 5 X 11¹ + 13 X 11² = 1653
Deze waarde komt niet overeen met de hashwaarde van ons patroon. Dus de string bestaat hier niet. Nu moeten we de volgende stap overwegen. Om de hash-waarde van onze volgende string- emi te berekenen. We kunnen dit berekenen met behulp van onze formule. Maar dat zou nogal triviaal zijn en ons meer kosten. In plaats daarvan gebruiken we een andere techniek.
- We trekken de waarde van de eerste letter van de vorige reeks af van onze huidige hashwaarde. In dit geval, y . We krijgen,
1653 - 25 = 1628. - We delen het verschil met onze priemgetal , die 11 is voor dit voorbeeld. We krijgen,
1628 / 11 = 148. - We voegen een nieuwe letter X (prime) ᵐ⁻¹ toe , waarbij m de lengte van het patroon is, met het quotiënt, dat i = 9 is . We krijgen
148 + 9 X 11² = 1237.
De nieuwe hashwaarde is niet gelijk aan onze hashwaarde voor patronen. Moving on, voor n krijgen we:
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
Het komt niet overeen. Daarna krijgen we voor 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
Het komt niet overeen. Vervolgens krijgen we voor een :
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
Het is een wedstrijd! Nu vergelijken we ons patroon met de huidige string. Omdat beide strings overeenkomen, bestaat de substring in deze string. En we keren terug naar de startpositie van onze substring.
De pseudo-code zal zijn:
Hash-berekening:
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
Hash herberekening:
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
String Match:
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
Als het algoritme geen overeenkomst vindt, retourneert het gewoon -1 .
Dit algoritme wordt gebruikt bij het detecteren van plagiaat. Gezien het bronmateriaal, kan het algoritme snel in een paper zoeken naar gevallen van zinnen uit het bronmateriaal, waarbij details zoals hoofdletters en leestekens worden genegeerd. Vanwege de overvloed aan gezochte reeksen, zijn zoekreeksen met één reeks hier onpraktisch. Nogmaals, het Knuth-Morris-Pratt-algoritme of het Boyer-Moore String Search-algoritme is een sneller algoritme voor het zoeken naar tekenreeksen met één patroon, dan Rabin-Karp . Het is echter een gekozen algoritme voor het zoeken naar meerdere patronen. Als we een groot aantal, bijvoorbeeld k, patronen met vaste lengte in een tekst willen vinden, kunnen we een eenvoudige variant van het Rabin-Karp-algoritme maken.
Voor tekst met lengte n en p patronen met gecombineerde lengte m , is de gemiddelde en best case looptijd O (n + m) in ruimte O (p) , maar de worst case time is O (nm) .
Inleiding tot het Knuth-Morris-Pratt (KMP) algoritme
Stel dat we een tekst en een patroon hebben . We moeten bepalen of het patroon in de tekst voorkomt of niet. Bijvoorbeeld:
+-------+---+---+---+---+---+---+---+---+
| 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 |
+---------+---+---+---+---+
Dit patroon bestaat in de tekst . Dus onze substring-zoekopdracht moet 3 retourneren, de index van de positie van waaruit dit patroon begint. Dus hoe werkt onze brute force substring-zoekprocedure?
Wat we meestal doen is: we beginnen bij de 0e index van de tekst en de 0e index van ons * patroon en we vergelijken Tekst [0] met Patroon [0] . Omdat ze niet overeenkomen, gaan we naar de volgende index van onze tekst en vergelijken we Tekst [1] met Patroon [0] . Omdat dit een overeenkomst is, verhogen we de index van ons patroon en de index van de tekst ook. We vergelijken Tekst [2] met Patroon [1] . Ze zijn ook een match. Volgens dezelfde eerder beschreven procedure vergelijken we nu Tekst [3] met Patroon [2] . Omdat ze niet overeenkomen, beginnen we vanaf de volgende positie waar we de match begonnen te vinden. Dat is index 2 van de tekst . We vergelijken Tekst [2] met Patroon [0] . Ze komen niet overeen. Vervolgens verhogen we de index van de tekst , we vergelijken tekst [3] met patroon [0] . Ze komen overeen. Opnieuw komen tekst [4] en patroon [1] overeen, tekst [5] en patroon [2] komen overeen en tekst [6] en patroon [3] komen overeen. Aangezien we het einde van ons patroon hebben bereikt, retourneren we nu de index van waaruit onze wedstrijd is gestart, dat is 3 . Als ons patroon was: bcgll , betekent dit dat als het patroon niet in onze tekst bestond, onze zoekopdracht uitzondering of -1 of een andere vooraf gedefinieerde waarde zou moeten opleveren. We kunnen duidelijk zien dat, in het ergste geval, dit algoritme O(mn) tijd zou nemen waarbij m de lengte van de tekst is en n de lengte van het patroon is . Hoe verminderen we deze tijdcomplexiteit? Dit is waar KMP Substring Search Algorithm in beeld komt.
Het Knuth-Morris-Pratt String-zoekalgoritme of KMP-algoritme zoekt naar voorkomen van een "patroon" in een hoofdtekst door de observatie te gebruiken dat wanneer een mismatch optreedt, het woord zelf voldoende informatie bevat om te bepalen waar de volgende wedstrijd kan beginnen , waardoor heronderzoek van eerder overeenkomende karakters wordt omzeild. Het algoritme werd in 1970 bedacht door Donuld Knuth en Vaughan Pratt en onafhankelijk door James H. Morris . Het trio publiceerde het gezamenlijk in 1977.
Laten we breiden ons voorbeeld tekst en Patroon voor een beter begrip:
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 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 |
+---------+---+---+---+---+---+---+---+---+
In eerste instantie komen onze tekst en patroon overeen met index 2 . Tekst [3] en patroon [3] komen niet overeen. Dus ons doel is om niet achteruit te gaan in deze tekst , dat wil zeggen dat we in geval van een mismatch niet willen dat onze matching opnieuw begint vanaf de positie waarmee we begonnen zijn te matchen. Om dat te bereiken, zoeken we naar een achtervoegsel in ons patroon vlak voordat onze mismatch plaatsvond (substring abc ), wat ook een voorvoegsel is van de substring van ons patroon . Omdat in ons voorbeeld alle tekens uniek zijn, is er geen achtervoegsel, dat is het voorvoegsel van onze overeenkomende substring. Dat betekent dus dat onze volgende vergelijking zal beginnen bij index 0 . Wacht even, je zult begrijpen waarom we dit hebben gedaan. Vervolgens vergelijken we Tekst [3] met Patroon [0] en het komt niet overeen. Daarna vinden we voor Tekst van index 4 tot index 9 en voor Patroon van index 0 tot index 5 een overeenkomst. We vinden een mismatch in Tekst [10] en Patroon [6] . Dus nemen we de substring van Pattern vlak voor het punt waar mismatch optreedt (substring abcdabc ), we controleren op een achtervoegsel, dat is ook een prefix van deze substring. We kunnen hier zien dat ab zowel het achtervoegsel als het voorvoegsel van deze substring is. Wat dat betekent is, omdat we tot Tekst [10] hebben gematcht, de tekens vlak voor de mismatch ab zijn . Wat we hieruit kunnen afleiden, is dat aangezien ab ook een voorvoegsel is van de substring die we hebben genomen, we ab niet opnieuw hoeven te controleren en de volgende controle kan beginnen bij Tekst [10] en Patroon [2] . We hoefden niet terug te kijken naar de hele tekst , we kunnen direct beginnen waar onze mismatch plaatsvond. Nu controleren we Tekst [10] en Patroon [2] , omdat het een mismatch is en de substring voor mismatch ( abc ) geen achtervoegsel bevat dat ook een voorvoegsel is, controleren we Tekst [10] en Patroon [0] , ze komen niet overeen. Daarna voor tekst van index 11 tot index 17 en voor patroon van index 0 tot index 6 . We vinden een mismatch in Tekst [18] en Patroon [7] . Dus nogmaals controleren we de substring vóór mismatch (substring abcdabc ) en vinden we dat abc zowel het achtervoegsel als het voorvoegsel is. Omdat we dus overeenkwamen met Patroon [7] , moet abc voor Tekst [18] staan . Dat betekent dat we niet hoeven te vergelijken tot Tekst [17] en onze vergelijking zal beginnen bij Tekst [18] en Patroon [3] . We zullen dus een wedstrijd vinden en we zullen 15 teruggeven die onze startindex van de wedstrijd is. Dit is hoe onze KMP Substring Search werkt met behulp van achtervoegsel- en prefixinformatie.
Hoe kunnen we nu efficiënt berekenen of het achtervoegsel hetzelfde is als het voorvoegsel en op welk punt we moeten controleren of er een verschil in teken bestaat tussen Tekst en Patroon . Laten we een voorbeeld bekijken:
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
We genereren een array met de vereiste informatie. Laten we de array S noemen. De grootte van de array is hetzelfde als de lengte van het patroon. Aangezien de eerste letter van het patroon niet het achtervoegsel van een voorvoegsel kan zijn, plaatsen we S [0] = 0 . We nemen eerst i = 1 en j = 0 . Bij elke stap vergelijken we Patroon [i] en Patroon [j] en increment i . Als er een overeenkomst is, plaatsen we S [i] = j + 1 en verhogen j , als er een mismatch is, controleren we de vorige waardepositie van j (indien beschikbaar) en stellen we j = S [j-1] in (als j is niet gelijk aan 0 ), we blijven dit doen totdat S [j] niet overeenkomt met S [i] of j niet 0 wordt . Voor de laatste zetten we S [i] = 0 . Voor ons voorbeeld:
j i
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
Patroon [j] en Patroon [i] komen niet overeen, dus we verhogen i en omdat j 0 is , controleren we de vorige waarde niet en plaatsen Patroon [i] = 0 . Als we i blijven verhogen, voor i = 4 , krijgen we een overeenkomst, dus zetten we S [i] = S [4] = j + 1 = 0 + 1 = 1 en increment j en i . Onze reeks ziet eruit als:
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 | | | |
+---------+---+---+---+---+---+---+---+---+
Omdat Patroon [1] en Patroon [5] een overeenkomst zijn, plaatsen we S [i] = S [5] = j + 1 = 1 + 1 = 2 . Als we doorgaan, vinden we een mismatch voor j = 3 en i = 7 . Omdat j niet gelijk is aan 0 , zetten we j = S [j-1] . En we vergelijken de tekens op i en j zijn hetzelfde of niet, omdat ze hetzelfde zijn, plaatsen we S [i] = j + 1. Onze voltooide array ziet er als volgt uit:
+---------+---+---+---+---+---+---+---+---+
| S | 0 | 0 | 0 | 0 | 1 | 2 | 3 | 1 |
+---------+---+---+---+---+---+---+---+---+
Dit is onze vereiste reeks. Hier een nul-waarde van S [i] middel zal een S [i] lengte suffix dezelfde als voorvoegsel dat subreeks (substring van 0 tot i) en de volgende vergelijking begint vanaf S [i] + 1-positie van de Patroon Ons algoritme om de array te genereren ziet er als volgt uit:
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
De tijdcomplexiteit om deze array te bouwen is O(n) en de ruimtecomplexiteit is ook O(n) . Om er zeker van te zijn dat u het algoritme volledig begrijpt, probeer dan een array voor patroon aabaabaa te genereren en controleer of het resultaat overeenkomt met deze .
Laten we nu een substring-zoekopdracht uitvoeren met behulp van het volgende voorbeeld:
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
| 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 |
+---------+---+---+---+---+---+---+
We hebben een tekst , een patroon en een vooraf berekende array S met behulp van onze eerder gedefinieerde logica. We vergelijken Tekst [0] en Patroon [0] en ze zijn hetzelfde. Tekst [1] en patroon [1] zijn hetzelfde. Tekst [2] en patroon [2] zijn niet hetzelfde. We controleren de waarde op de positie vlak voor de mismatch. Omdat S [1] 0 is , is er geen achtervoegsel dat hetzelfde is als het voorvoegsel in onze substring en onze vergelijking begint op positie S [1] , die 0 is . Patroon [0] is dus niet hetzelfde als Tekst [2] , dus we gaan verder. Tekst [3] is hetzelfde als Patroon [0] en er is een overeenkomst met Tekst [8] en Patroon [5] . We gaan een stap terug in de S- array en vinden 2 . Dit betekent dus dat er een voorvoegsel van lengte 2 is, dat ook het achtervoegsel is van deze substring ( abcab), die ab is . Dat betekent ook dat er een ab vóór Tekst staat [8] . Dus we kunnen patroon [0] en patroon [1] veilig negeren en onze volgende vergelijking starten vanaf patroon [2] en tekst [8] . Als we doorgaan, vinden we het patroon in de tekst . Onze procedure ziet er als volgt uit:
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
De tijdcomplexiteit van dit algoritme afgezien van de Suffix Array Calculation is O(m) . Aangezien GenerateSuffixArray O(n) , is de totale tijdcomplexiteit van KMP Algorithm: O(m+n) .
PS: als u meerdere exemplaren van Patroon in de tekst wilt vinden, in plaats van de waarde te retourneren, deze afdrukken / opslaan en j := S[j-1] . Houd ook een flag om bij te houden of u een gebeurtenis hebt gevonden of niet en behandel deze dienovereenkomstig.
Python Implementatie van KMP-algoritme.
Hooiberg : de tekenreeks waarin het gegeven patroon moet worden doorzocht.
Naald : het te doorzoeken patroon.
Tijdcomplexiteit: Zoeken gedeelte (strstr methode) heeft complexiteit O (n) waarbij n de lengte van hooiberg maar naald wordt ook vooraf ontleed voor het bouwen prefix tafel O (m) is vereist voor het bouwen prefix tafel waar m de lengte van de naald.
Daarom is de totale tijdcomplexiteit voor KMP O (n + m)
Ruimtecomplexiteit : O (m) vanwege prefixtabel op naald.
Opmerking: na de implementatie wordt de startpositie van de match in de hooiberg geretourneerd (als er een match is), anders wordt -1 geretourneerd, voor randgevallen zoals wanneer de naald / hooiberg een lege string is of de naald niet in de hooiberg wordt gevonden.
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)
