algorithm
Ricerca per sottostringa
Ricerca…
Algoritmo di KMP in C
Dato un testo txt e un pattern pat , l'obiettivo di questo programma sarà quello di stampare tutte le occured di pat in txt .
Esempi:
Ingresso:
txt[] = "THIS IS A TEST TEXT"
pat[] = "TEST"
produzione:
Pattern found at index 10
Ingresso:
txt[] = "AABAACAADAABAAABAA"
pat[] = "AABA"
produzione:
Pattern found at index 0
Pattern found at index 9
Pattern found at index 13
Implementazione del linguaggio 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;
}
Produzione:
Found pattern at index 10
Riferimento:
http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/
Introduzione all'algoritmo di Rabin-Karp
Rabin-Karp Algorithm è un algoritmo per la ricerca di stringhe creato da Richard M. Karp e Michael O. Rabin che utilizza l'hashing per trovare uno qualsiasi di un insieme di stringhe di pattern in un testo.
Una sottostringa di una stringa è un'altra stringa che si verifica in. Ad esempio, ver è una sottostringa di stackoverflow . Da non confondere con la sottosequenza perché la copertura è una sottosequenza della stessa stringa. In altre parole, qualsiasi sottoinsieme di lettere consecutive in una stringa è una sottostringa della stringa specificata.
Nell'algoritmo Rabin-Karp, genereremo un hash del nostro pattern che stiamo cercando e controlliamo se l'hash del nostro testo corrisponde al pattern o no. Se non corrisponde, possiamo garantire che il modello non esiste nel testo . Tuttavia, se corrisponde, il pattern può essere presente nel testo . Diamo un'occhiata a un esempio:
Diciamo che abbiamo un testo: yeminsajid e vogliamo scoprire se il pattern nsa esiste nel testo. Per calcolare l'hash e il rolling hash, dovremo utilizzare un numero primo. Questo può essere qualsiasi numero primo. Prendiamo Prime = 11 per questo esempio. Determineremo il valore hash usando questa formula:
(1st letter) X (prime) + (2nd letter) X (prime)¹ + (3rd letter) X (prime)² X + ......
Indicheremo:
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
Il valore hash di nsa sarà:
14 X 11⁰ + 19 X 11¹ + 1 X 11² = 344
Ora troviamo l'hash rolling del nostro testo. Se l'hash rotolante corrisponde al valore hash del nostro pattern, controlleremo se le stringhe corrispondono o meno. Dato che il nostro modello ha 3 lettere, prendiamo le prime 3 lettere yem dal nostro testo e calcoliamo il valore hash. Noi abbiamo:
25 X 11⁰ + 5 X 11¹ + 13 X 11² = 1653
Questo valore non corrisponde al valore hash del nostro modello. Quindi la stringa non esiste qui. Ora dobbiamo considerare il prossimo passo. Per calcolare il valore hash della nostra stringa successiva emi . Possiamo calcolare questo usando la nostra formula. Ma sarebbe piuttosto banale e ci costerebbe di più. Invece, usiamo un'altra tecnica.
- Sottraiamo il valore della prima lettera della stringa precedente dal nostro attuale valore di hash. In questo caso, y . Otteniamo,
1653 - 25 = 1628. - Dividiamo la differenza con il nostro primo , che è 11 per questo esempio. Otteniamo,
1628 / 11 = 148. - Aggiungiamo una nuova lettera X (primo) ᵐ⁻¹ , dove m è la lunghezza del modello, con il quoziente, che è i = 9 . Otteniamo,
148 + 9 X 11² = 1237.
Il nuovo valore di hash non è uguale al valore hash del nostro modello. Andando avanti, per n otteniamo:
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
Non corrisponde. Dopo ciò, per s , otteniamo:
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
Non corrisponde. Successivamente, per a , otteniamo:
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
È una partita! Ora confrontiamo il nostro modello con la stringa corrente. Poiché entrambe le stringhe corrispondono, la sottostringa esiste in questa stringa. E restituiamo la posizione iniziale della nostra sottostringa.
Lo pseudo-codice sarà:
Calcolo hash:
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
Ricalcolo 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
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
Se l'algoritmo non trova alcuna corrispondenza, restituisce semplicemente -1 .
Questo algoritmo viene utilizzato per rilevare il plagio. Dato il materiale sorgente, l'algoritmo può cercare rapidamente attraverso una carta per le istanze di frasi dal materiale di origine, ignorando dettagli come caso e punteggiatura. A causa dell'abbondanza delle stringhe ricercate, qui gli algoritmi di ricerca a stringa singola sono poco pratici. Ancora una volta, l' algoritmo di Knuth-Morris-Pratt o l' algoritmo di ricerca di stringhe Boyer-Moore è un algoritmo di ricerca di stringhe a pattern singolo più veloce di Rabin-Karp . Tuttavia, è un algoritmo di scelta per la ricerca di più modelli. Se vogliamo trovare uno qualsiasi dei numeri grandi, ad esempio k, modelli di lunghezza fissa in un testo, possiamo creare una semplice variante dell'algoritmo Rabin-Karp.
Per il testo di lunghezza n e p i modelli di lunghezza combinata m , la sua media e il miglior tempo di esecuzione del caso è O (n + m) nello spazio O (p) , ma il suo caso peggiore è O (nm) .
Introduzione all'algoritmo di Knuth-Morris-Pratt (KMP)
Supponiamo di avere un testo e un motivo . Abbiamo bisogno di determinare se il modello esiste nel testo o no. Per esempio:
+-------+---+---+---+---+---+---+---+---+
| 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 |
+---------+---+---+---+---+
Questo modello esiste nel testo . Quindi la nostra ricerca di sottostringa dovrebbe restituire 3 , l'indice della posizione da cui questo modello inizia. Quindi, come funziona la nostra procedura di ricerca della sottostringa a forza bruta?
Quello che facciamo di solito è: partiamo dall'indice 0 del testo e dall'indice 0 del nostro modello * e confrontiamo il testo [0] con Pattern [0] . Dal momento che non sono una corrispondenza, andiamo al prossimo indice del nostro testo e confrontiamo il testo [1] con Pattern [0] . Poiché si tratta di una corrispondenza, incrementiamo anche l'indice del nostro modello e l'indice del testo . Confrontiamo il testo [2] con Pattern [1] . Sono anche una partita. Seguendo la stessa procedura indicata in precedenza, ora confrontiamo il testo [3] con Pattern [2] . Poiché non corrispondono, iniziamo dalla posizione successiva in cui abbiamo iniziato a trovare la corrispondenza. Quello è l'indice 2 del testo . Confrontiamo il testo [2] con Pattern [0] . Non corrispondono Quindi incrementando l'indice del testo , confrontiamo il testo [3] con Pattern [0] . Corrispondono. Ancora Testo [4] e Pattern [1] corrispondono, Testo [5] e Pattern [2] corrispondono e Testo [6] e Pattern [3] corrispondono. Dal momento che abbiamo raggiunto la fine del nostro Pattern , ora restituiamo l'indice da cui è partita la nostra partita, ovvero 3 . Se il nostro modello era: bcgll , ciò significa che se il pattern non esisteva nel nostro testo , la nostra ricerca dovrebbe restituire l'eccezione o -1 o qualsiasi altro valore predefinito. Possiamo vedere chiaramente che, nel peggiore dei casi, questo algoritmo impiegherebbe il tempo di O(mn) dove m è la lunghezza del testo e n è la lunghezza del modello . Come riduciamo questa complessità temporale? È qui che entra in gioco l'algoritmo di ricerca delle sottostringhe KMP.
L' algoritmo di ricerca delle stringhe Knuth-Morris-Pratt o KMP Algorithm ricerca le occorrenze di un "Pattern" all'interno di un "testo" principale utilizzando l'osservazione che quando si verifica una mancata corrispondenza, la parola stessa incorpora informazioni sufficienti per determinare dove potrebbe iniziare la prossima partita , evitando così il riesame dei caratteri precedentemente abbinati. L'algoritmo è stato concepito nel 1970 da Donuld Knuth e Vaughan Pratt e indipendentemente da James H. Morris . Il trio l'ha pubblicato insieme nel 1977.
Estendiamo il nostro esempio Testo e Pattern per una migliore comprensione:
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 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 un primo momento, il nostro testo e il modello corrispondono fino all'indice 2 . Testo [3] e Pattern [3] non corrispondono. Quindi il nostro scopo è di non andare indietro in questo testo , cioè, in caso di disallineamento, non vogliamo che il nostro abbinamento ricominci dalla posizione con cui abbiamo iniziato a fare i conti. Per riuscirci, cercheremo un suffisso nel nostro Pattern subito prima della nostra discrepanza (sottostringa abc ), che è anche un prefisso della sottostringa del nostro Pattern . Per il nostro esempio, dal momento che tutti i caratteri sono unici, non esiste un suffisso, ovvero il prefisso della nostra sottostringa corrispondente. Quindi, questo significa che il nostro prossimo confronto inizierà dall'indice 0 . Aspetta un attimo, capirai perché lo abbiamo fatto. Successivamente, confrontiamo il testo [3] con Pattern [0] e non corrisponde. Dopodiché, per Testo dall'indice 4 all'indice 9 e per Pattern dall'indice 0 all'indice 5 , troviamo una corrispondenza. Troviamo una mancata corrispondenza in Testo [10] e Modello [6] . Quindi prendiamo la sottostringa da Pattern appena prima del punto in cui si verifica la mancata corrispondenza (sottostringa abcdabc ), controlliamo un suffisso, che è anche un prefisso di questa sottostringa. Possiamo vedere qui ab sia il suffisso che il prefisso di questa sottostringa. Ciò significa che, poiché abbiamo abbinato fino a Testo [10] , i caratteri immediatamente prima della mancata corrispondenza sono ab . Quello che possiamo dedurre da questo è che poiché ab è anche un prefisso della sottostringa che abbiamo preso, non dobbiamo controllare nuovamente ab e il successivo controllo può iniziare da Testo [10] e Pattern [2] . Non abbiamo dovuto guardare indietro a tutto il testo , possiamo iniziare direttamente da dove si è verificata la nostra mancata corrispondenza. Ora controlliamo Text [10] e Pattern [2] , poiché si tratta di una mancata corrispondenza, e la sottostringa prima della mismatch ( abc ) non contiene un suffisso che è anche un prefisso, controlliamo Text [10] e Pattern [0] , non corrispondono Dopodiché, per Testo dall'indice 11 all'indice 17 e per Pattern dall'indice 0 all'indice 6 . Troviamo una mancata corrispondenza in Testo [18] e Pattern [7] . Quindi, di nuovo controlliamo la sottostringa prima della mancata corrispondenza (sottostringa abcdabc ) e troviamo che abc è sia il suffisso che il prefisso. Quindi, dato che abbiamo abbinato fino a Pattern [7] , abc deve essere prima di Text [18] . Ciò significa che non abbiamo bisogno di confrontare fino a Testo [17] e il nostro confronto inizierà da Testo [18] e Pattern [3] . Quindi troveremo una corrispondenza e restituiremo 15 che è il nostro indice iniziale della partita. Questo è il modo in cui la nostra ricerca di substring KMP funziona utilizzando le informazioni sul suffisso e sul prefisso.
Ora, come calcoliamo in modo efficiente se il suffisso è uguale al prefisso ea quale punto avviare il controllo se c'è una mancata corrispondenza di carattere tra Testo e Motivo . Diamo un'occhiata a un esempio:
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
Genereremo una matrice contenente le informazioni richieste. Chiamiamo la matrice S. La dimensione dell'array sarà uguale alla lunghezza del pattern. Poiché la prima lettera del Pattern non può essere il suffisso di alcun prefisso, inseriremo S [0] = 0 . Prendiamo i = 1 e j = 0 all'inizio. Ad ogni passo confrontiamo Pattern [i] e Pattern [j] e incrementiamo i . Se c'è una corrispondenza, inseriamo S [i] = j + 1 e incrementa j , se c'è una mancata corrispondenza, controlliamo la posizione del valore precedente di j (se disponibile) e impostiamo j = S [j-1] (se j non è uguale a 0 ), continuiamo a farlo finché S [j] non corrisponde a S [i] o j non diventa 0 . Per il successivo, abbiamo messo S [i] = 0 . Per il nostro esempio:
j i
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
Pattern [j] e Pattern [i] non corrispondono, quindi incrementiamo i e poiché j è 0 , non controlliamo il valore precedente e mettiamo Pattern [i] = 0 . Se continuiamo ad incrementare i , per i = 4 , otterremo una corrispondenza, quindi inseriamo S [i] = S [4] = j + 1 = 0 + 1 = 1 e incrementa j e i . Il nostro array sarà simile a:
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 | | | |
+---------+---+---+---+---+---+---+---+---+
Poiché Pattern [1] e Pattern [5] sono una corrispondenza, abbiamo inserito S [i] = S [5] = j + 1 = 1 + 1 = 2 . Se continuiamo, troveremo una discrepanza per j = 3 e i = 7 . Poiché j non è uguale a 0 , poniamo j = S [j-1] . E confronteremo i personaggi di i e j sono uguali o no, dato che sono uguali, metteremo S [i] = j + 1. La nostra matrice completata sarà simile a:
+---------+---+---+---+---+---+---+---+---+
| S | 0 | 0 | 0 | 0 | 1 | 2 | 3 | 1 |
+---------+---+---+---+---+---+---+---+---+
Questa è la nostra matrice richiesta. Qui un valore diverso da S [i] significa che c'è un suffisso S [i] uguale al prefisso in quella sottostringa (sottostringa da 0 a i ) e il confronto successivo inizierà da S [i] + 1 posizione del Modello Il nostro algoritmo per generare l'array sarebbe simile a:
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 complessità temporale per costruire questo array è O(n) e anche la complessità dello spazio è O(n) . Per assicurarti di aver compreso completamente l'algoritmo, prova a generare un array per pattern aabaabaa e controlla se il risultato corrisponde a questo .
Ora facciamo una ricerca di sottostringa usando il seguente esempio:
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
| 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 |
+---------+---+---+---+---+---+---+
Abbiamo un testo , un pattern e un array S precalcolato che utilizza la nostra logica definita in precedenza. Confrontiamo il testo [0] e il pattern [0] e sono gli stessi. Testo [1] e Pattern [1] sono uguali. Testo [2] e Pattern [2] non sono uguali. Controlliamo il valore nella posizione immediatamente prima della mancata corrispondenza. Poiché S [1] è 0 , non esiste un suffisso uguale al prefisso nella nostra sottostringa e il nostro confronto inizia dalla posizione S [1] , che è 0 . Quindi Pattern [0] non è uguale a Testo [2] , quindi procediamo. Il testo [3] è uguale a Pattern [0] e c'è una corrispondenza fino a Testo [8] e Pattern [5] . Facciamo un passo indietro nell'array S e troviamo 2 . Quindi questo significa che c'è un prefisso di lunghezza 2 che è anche il suffisso di questa sottostringa ( abcab) che è ab . Ciò significa anche che c'è un ab prima del testo [8] . Quindi possiamo tranquillamente ignorare Pattern [0] e Pattern [1] e iniziare il nostro prossimo confronto con Pattern [2] e Text [8] . Se continuiamo, troveremo il Pattern nel testo . La nostra procedura sarà simile a:
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 complessità temporale di questo algoritmo oltre al calcolo dell'array Suffix è O(m) . Poiché GenerateSuffixArray richiede O(n) , la complessità temporale totale di KMP Algorithm è: O(m+n) .
PS: Se vuoi trovare più occorrenze di Pattern nel testo , invece di restituire il valore, stampalo / memorizzalo e imposta j := S[j-1] . Inoltre, tieni traccia di una flag per sapere se hai trovato o meno un'occorrenza e gestirla di conseguenza.
Implementazione Python dell'algoritmo KMP.
Haystack : la stringa in cui è necessario cercare il dato pattern.
Ago : il modello da cercare.
Complessità del tempo : la porzione di ricerca (metodo strstr) ha la complessità O (n) dove n è la lunghezza del pagliaio ma come ago è anche pre-elaborato per la tabella del prefisso dell'edificio O (m) è richiesta per la tabella del prefisso di costruzione dove m è la lunghezza di l'ago.
Pertanto, la complessità complessiva del tempo per KMP è O (n + m)
Complessità dello spazio : O (m) a causa della tabella dei prefissi sull'ago.
Nota: la seguente implementazione restituisce la posizione iniziale della partita nel pagliaio (se c'è una corrispondenza) altrimenti restituisce -1, per i casi limite come se ago / pagliaio è una stringa vuota o l'ago non viene trovato nel pagliaio.
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)