algorithm
Recherche de sous-chaîne
Recherche…
Algorithme KMP en C
Étant donné un texte txt et un motif pat , l'objectif de ce programme sera d'imprimer toute l'occurrence de pat dans txt .
Exemples:
Contribution:
txt[] = "THIS IS A TEST TEXT"
pat[] = "TEST"
sortie:
Pattern found at index 10
Contribution:
txt[] = "AABAACAADAABAAABAA"
pat[] = "AABA"
sortie:
Pattern found at index 0
Pattern found at index 9
Pattern found at index 13
Implémentation du langage 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;
}
Sortie:
Found pattern at index 10
Référence:
http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/
Introduction à l'algorithme de Rabin-Karp
L'algorithme de Rabin-Karp est un algorithme de recherche de chaîne créé par Richard M. Karp et Michael O. Rabin qui utilise le hachage pour trouver un ensemble de chaînes de motifs dans un texte.
Une sous-chaîne d'une chaîne est une autre chaîne qui se produit. Par exemple, ver est une sous-chaîne de stackoverflow . Ne pas confondre avec la sous-séquence car cover est une sous-séquence de la même chaîne. En d'autres termes, tout sous-ensemble de lettres consécutives dans une chaîne est une sous-chaîne de la chaîne donnée.
Dans l'algorithme Rabin-Karp, nous allons générer un hachage de notre modèle que nous recherchons et vérifier si le hachage de notre texte correspond ou non au modèle . Si cela ne correspond pas, nous pouvons garantir que le motif n'existe pas dans le texte . Cependant, si elle correspond, le motif peut être présent dans le texte . Regardons un exemple:
Disons que nous avons un texte: yeminsajid et nous voulons savoir si le motif nsa existe dans le texte. Pour calculer le hachage et le hash roulant, nous devons utiliser un nombre premier. Cela peut être n'importe quel nombre premier. Prenons premier = 11 pour cet exemple. Nous déterminerons la valeur de hachage en utilisant cette formule:
(1st letter) X (prime) + (2nd letter) X (prime)¹ + (3rd letter) X (prime)² X + ......
On notera:
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
La valeur de hachage de nsa sera:
14 X 11⁰ + 19 X 11¹ + 1 X 11² = 344
Maintenant, nous trouvons le hash roulant de notre texte. Si le hash roulant correspond à la valeur de hachage de notre modèle, nous vérifierons si les chaînes correspondent ou non. Étant donné que notre modèle a 3 lettres, nous allons prendre la 1ère 3 lettres YEM de notre texte et calcul de la valeur de hachage. On a:
25 X 11⁰ + 5 X 11¹ + 13 X 11² = 1653
Cette valeur ne correspond pas à la valeur de hachage de notre modèle. Donc la chaîne n'existe pas ici. Maintenant, nous devons envisager l'étape suivante. Pour calculer la valeur de hachage de notre prochaine chaîne emi . Nous pouvons calculer cela en utilisant notre formule. Mais cela serait plutôt trivial et nous coûterait plus cher. Au lieu de cela, nous utilisons une autre technique.
- Nous soustrayons la valeur de la première lettre de la chaîne précédente de notre valeur de hachage actuelle. Dans ce cas, y . Nous obtenons,
1653 - 25 = 1628. - Nous divisons la différence avec notre nombre premier , qui est 11 pour cet exemple. Nous obtenons,
1628 / 11 = 148. - Nous ajoutons la nouvelle lettre X (premier) ᵐ⁻¹ , où m est la longueur du motif, avec le quotient qui est i = 9 . Nous obtenons,
148 + 9 X 11² = 1237.
La nouvelle valeur de hachage n'est pas égale à la valeur de hachage de nos modèles. Sur la route , pour n nous obtenons:
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
Ça ne correspond pas Après cela, pour s , nous obtenons:
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 ne correspond pas Ensuite, pour un , nous obtenons:
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
C'est un match! Maintenant, nous comparons notre modèle avec la chaîne actuelle. Comme les deux chaînes correspondent, la sous-chaîne existe dans cette chaîne. Et nous retournons la position de départ de notre sous-chaîne.
Le pseudo-code sera:
Calcul de hachage:
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
Recalcul de hachage:
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
Match de cordes:
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
Si l'algorithme ne trouve aucune correspondance, il renvoie simplement -1 .
Cet algorithme est utilisé pour détecter le plagiat. Étant donné le matériel source, l'algorithme peut rapidement parcourir un article pour trouver des exemples de phrases à partir du matériau source, en ignorant des détails tels que la casse et la ponctuation. En raison de l’abondance des chaînes recherchées, les algorithmes de recherche à chaîne unique sont peu pratiques ici. Encore une fois, l' algorithme de Knuth-Morris-Pratt ou l' algorithme de recherche de chaîne de Boyer-Moore est un algorithme de recherche de chaîne à motif unique plus rapide que celui de Rabin-Karp . Cependant, c'est un algorithme de choix pour la recherche de motifs multiples. Si nous voulons trouver l'un des grands nombres, disons k, des motifs de longueur fixe dans un texte, nous pouvons créer une variante simple de l'algorithme de Rabin-Karp.
Pour le texte des motifs de longueur n et p de longueur combinée m , sa durée de fonctionnement moyenne et meilleure est O (n + m) dans l'espace O (p) , mais sa pire période est O (nm) .
Introduction à l'algorithme de Knuth-Morris-Pratt (KMP)
Supposons que nous ayons un texte et un motif . Nous devons déterminer si le modèle existe ou non dans le texte. Par exemple:
+-------+---+---+---+---+---+---+---+---+
| 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 |
+---------+---+---+---+---+
Ce modèle existe dans le texte . Donc, notre recherche de sous-chaîne doit retourner 3 , l’index de la position à partir de laquelle ce modèle commence. Alors, comment fonctionne notre procédure de recherche de sous-chaîne par force brute?
Ce que nous faisons habituellement est: nous partons du 0ème index du texte et du 0ème index de notre * pattern et nous comparons Text [0] avec Pattern [0] . Comme ils ne correspondent pas, nous allons au prochain index de notre texte et nous comparons Text [1] avec Pattern [0] . Comme il s'agit d'une correspondance, nous incrémentons également l'index de notre modèle et l'index du texte . Nous comparons Text [2] avec Pattern [1] . Ils sont aussi un match. En suivant la même procédure que précédemment, nous comparons maintenant Text [3] avec Pattern [2] . Comme ils ne correspondent pas, nous partons de la position suivante où nous avons commencé à trouver le match. C'est l'index 2 du texte . Nous comparons Text [2] avec Pattern [0] . Ils ne correspondent pas. Puis en incrémentant l’index du Text , on compare Text [3] avec Pattern [0] . Ils correspondent. De nouveau Text [4] et Pattern [1] correspondent, Text [5] et Pattern [2] correspondent et Text [6] et Pattern [3] correspondent. Comme nous avons atteint la fin de notre modèle , nous retournons maintenant l’index à partir duquel notre correspondance a commencé, à savoir 3 . Si notre modèle était: bcgll , cela signifie que si le modèle n'existait pas dans notre texte , notre recherche devrait renvoyer une exception ou -1 ou toute autre valeur prédéfinie. Nous pouvons clairement voir que, dans le pire des cas, cet algorithme prendrait O(mn) temps où m est la longueur du texte et n la longueur du motif . Comment pouvons-nous réduire cette complexité temporelle? C'est là que l'algorithme de recherche de sous-chaîne KMP entre en jeu.
L' algorithme de recherche de chaînes Knuth-Morris-Pratt ou l' algorithme KMP recherche les occurrences d'un "motif" dans un "texte" principal en utilisant l'observation selon laquelle, en cas d'incompatibilité, le mot lui-même contient suffisamment d'informations pour déterminer où , contournant ainsi le réexamen des caractères précédemment appariés. L'algorithme a été conçu en 1970 par Donuld Knuth et Vaughan Pratt et indépendamment par James H. Morris . Le trio l'a publié conjointement en 1977.
Étendons notre exemple Text and Pattern pour une meilleure compréhension:
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 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 |
+---------+---+---+---+---+---+---+---+---+
Au début, nos correspondances textuelles et graphiques jusqu’à l’index 2 . Le texte [3] et le motif [3] ne correspondent pas. Notre objectif est donc de ne pas revenir en arrière dans ce texte , c’est-à-dire qu’en cas de non-concordance, nous ne voulons pas que notre correspondance reprenne à partir de la position avec laquelle nous avons commencé à correspondre. Pour y parvenir, nous chercherons un suffixe dans notre Pattern juste avant que notre discordance ne se produise (sous-chaîne abc ), qui est également un préfixe de la sous-chaîne de notre Pattern . Pour notre exemple, puisque tous les caractères sont uniques, il n'y a pas de suffixe, c'est le préfixe de notre sous-chaîne correspondante. Donc, cela signifie que notre prochaine comparaison commencera à partir de l’index 0 . Attends un peu, tu comprendras pourquoi nous avons fait ça. Ensuite, nous comparons Text [3] avec Pattern [0] et cela ne correspond pas. Après cela, pour Text from index 4 to index 9 et pour Pattern de l'index 0 à l'index 5 , nous trouvons une correspondance. Nous trouvons un décalage dans Text [10] et Pattern [6] . Nous prenons donc la sous-chaîne de Pattern juste avant le point où la discordance se produit (sous-chaîne abcdabc ), nous vérifions un suffixe, qui est aussi un préfixe de cette sous-chaîne. Nous pouvons voir ici que ab est à la fois le suffixe et le préfixe de cette sous-chaîne. Ce que cela signifie, puisque nous avons comparé jusqu'à Text [10] , les caractères juste avant la disparité sont ab . On peut en déduire que puisque ab est aussi un préfixe de la sous-chaîne que nous avons prise, il n'est pas nécessaire de vérifier à nouveau ab et le prochain contrôle peut commencer par Text [10] et Pattern [2] . Nous n'avons pas eu à revenir sur l'ensemble du texte , nous pouvons commencer directement à partir de l'endroit où notre inadéquation s'est produite. Maintenant, nous vérifions Text [10] et Pattern [2] , car il ne correspond pas, et la sous-chaîne avant mismatch ( abc ) ne contient pas de suffixe qui est aussi un préfixe, nous vérifions Text [10] et Pattern [0] , ils ne correspondent pas. Après cela pour le texte de l'index 11 à l'index 17 et pour le motif de l'index 0 à l'index 6 . Nous trouvons une disparité dans Text [18] et Pattern [7] . Donc, encore une fois, nous vérifions la sous-chaîne avant la non-concordance (sous-chaîne abcdabc ) et trouvons que abc est à la fois le suffixe et le préfixe. Donc, puisque nous avons fait correspondre jusqu'à Pattern [7] , abc doit être avant Text [18] . Cela signifie que nous n'avons pas besoin de comparer jusqu'à ce que Text [17] et notre comparaison commence par Text [18] et Pattern [3] . Nous allons donc trouver une correspondance et nous retournerons 15 qui est notre index de départ du match. Voici comment notre recherche de sous-chaînes KMP fonctionne en utilisant les informations de suffixe et de préfixe.
Maintenant, comment pouvons-nous calculer efficacement si le suffixe est le même que le préfixe et à quel moment démarrer le contrôle s’il ya une incohérence de caractère entre le texte et le motif . Regardons un exemple:
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
Nous allons générer un tableau contenant les informations requises. Appelons le tableau S. La taille du tableau sera la même que la longueur du motif. Puisque la première lettre du Pattern ne peut être le suffixe d'aucun préfixe, nous allons mettre S [0] = 0 . Nous prenons d'abord i = 1 et j = 0 . A chaque étape, nous comparons le motif [i] et le motif [j] et incrémentons i . S'il y a une correspondance, on met S [i] = j + 1 et l'incrément j , s'il y a une discordance, on vérifie la position précédente de j (si disponible) et on met j = S [j-1] (si j n'est pas égal à 0 ), nous continuons à le faire jusqu'à ce que S [j] ne corresponde pas à S [i] ou que j ne devienne pas 0 . Pour le dernier, nous mettons S [i] = 0 . Pour notre exemple:
j i
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
Pattern [j] et Pattern [i] ne correspondent pas, donc nous incrémentons i et comme j vaut 0 , nous ne vérifions pas la valeur précédente et mettons Pattern [i] = 0 . Si nous continuons à incrémenter i , pour i = 4 , nous obtiendrons une correspondance, nous avons donc mis S [i] = S [4] = j + 1 = 0 + 1 = 1 et incrémenté j et i . Notre tableau ressemblera à:
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 | | | |
+---------+---+---+---+---+---+---+---+---+
Comme Pattern [1] et Pattern [5] correspondent, nous mettons S [i] = S [5] = j + 1 = 1 + 1 = 2 . Si nous continuons, nous trouverons une incompatibilité pour j = 3 et i = 7 . Puisque j n'est pas égal à 0 , on met j = S [j-1] . Et nous comparerons les caractères à i et j sont identiques ou non, puisqu'ils sont identiques, nous allons mettre S [i] = j + 1. Notre tableau terminé ressemblera à:
+---------+---+---+---+---+---+---+---+---+
| S | 0 | 0 | 0 | 0 | 1 | 2 | 3 | 1 |
+---------+---+---+---+---+---+---+---+---+
Ceci est notre tableau requis. Ici, une valeur non nulle de S [i] signifie qu'il y a un suffixe de longueur S [i] identique au préfixe dans cette sous-chaîne (sous-chaîne de 0 à i ) et la comparaison suivante commencera à partir de S [i] + 1 position du Motif Notre algorithme pour générer le tableau ressemblerait à ceci:
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
La complexité temporelle pour construire ce tableau est O(n) et la complexité de l'espace est également O(n) . Pour vous assurer que vous avez bien compris l’algorithme, essayez de générer un tableau pour le motif aabaabaa et vérifiez si le résultat correspond à celui- ci.
Faisons maintenant une recherche de sous-chaîne à l'aide de l'exemple suivant:
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
| 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 |
+---------+---+---+---+---+---+---+
Nous avons un texte , un motif et un tableau pré-calculé S en utilisant notre logique définie précédemment. Nous comparons Text [0] et Pattern [0] et ils sont identiques. Le texte [1] et le motif [1] sont identiques. Le texte [2] et le motif [2] ne sont pas identiques. Nous vérifions la valeur à la position juste avant la disparité. Puisque S [1] vaut 0 , il n'y a pas de suffixe identique au préfixe de notre sous-chaîne et notre comparaison commence à la position S [1] , qui est 0 . Donc, le Pattern [0] n'est pas le même que Text [2] , donc nous continuons. Le texte [3] est identique au motif [0] et il y a une correspondance jusqu'à Texte [8] et Motif [5] . Nous revenons en arrière dans le tableau S et trouvons 2 . Cela signifie donc qu'il y a un préfixe de longueur 2 qui est aussi le suffixe de cette sous-chaîne ( abcab) qui est ab . Cela signifie également qu'il y a un ab avant Text [8] . Nous pouvons donc ignorer en toute sécurité Pattern [0] et Pattern [1] et commencer notre prochaine comparaison avec Pattern [2] et Text [8] . Si nous continuons, nous trouverons le motif dans le texte . Notre procédure ressemblera à:
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
La complexité temporelle de cet algorithme en dehors du calcul du tableau de suffixes est O(m) . Puisque GenerateSuffixArray prend O(n) , la complexité temporelle totale de l’algorithme KMP est: O(m+n) .
PS: Si vous voulez trouver plusieurs occurrences de Pattern dans le texte , au lieu de retourner la valeur, imprimez-la / stockez-la et définissez j := S[j-1] . Conservez également un flag pour savoir si vous avez trouvé une occurrence ou non et gérez-la en conséquence.
Python Implémentation de l'algorithme KMP.
Botte de foin : Chaîne dans laquelle le modèle doit être recherché.
Aiguille : Le motif à rechercher.
Complexité du temps: partie de la recherche (méthode de strstr) a la complexité O (n) , où n est la longueur de la meule mais est nécessaire que l' aiguille est pré analysé également pour la construction de tableau de préfixes O (m) pour la construction de tableau de préfixes où m est la longueur de l'aiguille.
Par conséquent, la complexité temporelle globale de KMP est O (n + m)
Complexité de l'espace : O (m) à cause du tableau de préfixes sur l'aiguille.
Note: La suite de l'implémentation retourne la position de départ de la correspondance dans une botte de foin (s'il y a une correspondance) sinon renvoie -1, pour les cas limites comme si l'aiguille / haystack est une chaîne vide ou une aiguille.
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)