algorithm
Substrings Search
Sök…
KMP Algoritm i C
Givet en texttxt och ett mönster klapp är målet med detta program att skriva ut all förekomst av pat i txt .
Exempel:
Inmatning:
txt[] = "THIS IS A TEST TEXT"
pat[] = "TEST"
produktion:
Pattern found at index 10
Inmatning:
txt[] = "AABAACAADAABAAABAA"
pat[] = "AABA"
produktion:
Pattern found at index 0
Pattern found at index 9
Pattern found at index 13
C Språkimplementering:
// 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;
}
Produktion:
Found pattern at index 10
Referens:
http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/
Introduktion till Rabin-Karp algoritm
Rabin-Karp algoritm är en strängsökande algoritm skapad av Richard M. Karp och Michael O. Rabin som använder hashing för att hitta någon av en uppsättning mönstersträngar i en text.
En substring av en sträng är en annan sträng som inträffar i. Till exempel är ver en substring av stackoverflow . Inte att förväxla med efterföljande eftersom omslag är en efterföljning av samma sträng. Med andra ord är varje delmängd av på varandra följande bokstäver i en sträng en substring av den givna strängen.
I Rabin-Karp-algoritmen genererar vi en hash av vårt mönster som vi letar efter och kontrollerar om den rullande hashen i vår text matchar mönstret eller inte. Om det inte stämmer, kan vi garantera att mönstret inte finns i texten . Men om det stämmer, kan mönstret förekomma i texten. Låt oss titta på ett exempel:
Låt oss säga att vi har en text: yeminsajid och vi vill ta reda på om mönstret nsa finns i texten. För att beräkna hash och rullande hash måste vi använda ett primtal. Detta kan vara valfritt primtal. Låt oss ta prime = 11 för det här exemplet. Vi bestämmer hashvärde med hjälp av denna formel:
(1st letter) X (prime) + (2nd letter) X (prime)¹ + (3rd letter) X (prime)² X + ......
Vi kommer att beteckna:
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
Hashvärdet för nsa är:
14 X 11⁰ + 19 X 11¹ + 1 X 11² = 344
Nu hittar vi rullande hash i vår text. Om den rullande hashen matchar hashvärdet för vårt mönster, kontrollerar vi om strängarna matchar eller inte. Eftersom vår mönster har 3 bokstäver, tar vi 1: a 3 bokstäver yem från vår text och beräkna hash-värde. Vi får:
25 X 11⁰ + 5 X 11¹ + 13 X 11² = 1653
Detta värde stämmer inte med vårt mönster hashvärde. Så strängen finns inte här. Nu måste vi överväga nästa steg. För att beräkna hashvärdet för vår nästa strängemi . Vi kan beräkna detta med vår formel. Men det skulle vara ganska trivialt och kosta oss mer. Istället använder vi en annan teknik.
- Vi subtraherar värdet på First Letter of Previous String från vårt nuvarande hash-värde. I det här fallet, y . Vi får,
1653 - 25 = 1628. - Vi delar skillnaden med vår prime , som är 11 för detta exempel. Vi får
1628 / 11 = 148. - Vi lägger till en ny bokstav X (prim) where , där m är längden på mönstret, med kvoten, som är i = 9 . Vi får
148 + 9 X 11² = 1237.
Det nya hashvärdet är inte lika med våra mönster hashvärde. Fortsätter vi, för n får vi:
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
Det stämmer inte. Efter det, för s , får vi:
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
Det stämmer inte. Nästa, för a, får vi:
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
Det är en match! Nu jämför vi vårt mönster med den aktuella strängen. Eftersom båda strängarna matchar finns existerande sträng i den här strängen. Och vi returnerar utgångspositionen för vår substring.
Pseudokoden kommer att vara:
Hashberäkning:
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
Beräkning av 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
Om algoritmen inte hittar någon matchning returnerar den helt enkelt -1 .
Denna algoritm används för att upptäcka plagiering. Med tanke på källmaterial kan algoritmen snabbt söka igenom ett papper efter instanser av meningar från källmaterialet, och ignorera detaljer som fall och skiljetecken. På grund av överflödet av de sökta strängarna är algoritmer med ensträngssökning opraktiska här. Återigen är Knuth-Morris-Pratt-algoritmen eller Boyer-Moore String Search-algoritmen snabbare enmönstersträngssökningsalgoritm än Rabin-Karp . Det är emellertid en algoritm som du kan välja för sökning med flera mönster. Om vi vill hitta något av det stora antalet, säg k, mönster med fast längd i en text, kan vi skapa en enkel variant av Rabin-Karp-algoritmen.
För text av längd n och p- mönster med kombinerad längd m är dess genomsnittliga och bästa fallkörningstid O (n + m) i rymden O (p) , men dess värsta fall är O (nm) .
Introduktion till Knuth-Morris-Pratt (KMP) algoritm
Anta att vi har en text och ett mönster . Vi måste avgöra om mönstret finns i texten eller inte. Till exempel:
+-------+---+---+---+---+---+---+---+---+
| 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 |
+---------+---+---+---+---+
Detta mönster finns i texten . Så vår substring-sökning bör returnera 3 , indexet för den position från vilken detta mönster börjar. Så hur fungerar vår brute force substring search procedure?
Vad vi vanligtvis gör är: vi börjar från det 0: e indexet för texten och det 0: e indexet för vårt * mönster och vi jämför text [0] med Mönster [0] . Eftersom de inte är en matchning går vi till nästa index i vår text och vi jämför text [1] med Mönster [0] . Eftersom detta är en matchning, ökar vi indexet för vårt mönster och indexet för texten . Vi jämför text [2] med mönster [1] . De är också en match. Genom att följa samma procedur som nämnts tidigare jämför vi nu Text [3] med Mönster [2] . Eftersom de inte matchar, börjar vi från nästa position där vi började hitta matchen. Det är index 2 i texten . Vi jämför text [2] med mönster [0] . De matchar inte. Sedan ökar texten index, jämför vi Text [3] med Mönster [0] . De matchar. Återigen matchar Text [4] och Mönster [1], Match [Text] och Mönster [2] och Text [6] och Mönster [3] . Sedan vi har kommit till slutet av vårt mönster returnerar vi nu indexet från vilket vår match började, det vill säga 3 . Om vårt mönster var: bcgll , betyder det att om mönstret inte fanns i vår text , bör vår sökning returnera undantag eller -1 eller något annat fördefinierat värde. Vi kan tydligt se att i värsta fall skulle denna algoritm ta O(mn) tid där m är längden på texten och n är längden på mönstret . Hur minskar vi denna tidskomplexitet? Det är här KMP Substring Search Algoritm kommer in i bilden.
Knuth-Morris-Pratt-strängen som söker algoritm eller KMP-algoritmen söker efter förekomster av ett "mönster" inom en huvudtext "text" genom att använda den iakttagelsen att när en missanpassning inträffar, förkroppsligar sig själva ordet tillräcklig information för att avgöra var nästa match kan börja , och därmed kringgå omprövning av tidigare matchade tecken. Algoritmen utformades 1970 av Donuld Knuth och Vaughan Pratt och oberoende av James H. Morris . Trioen publicerade den gemensamt 1977.
Låt oss utöka vårt exempel Text och mönster för bättre förståelse:
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 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 |
+---------+---+---+---+---+---+---+---+---+
Först matchar vår text och mönster till index 2 . Text [3] och mönster [3] stämmer inte. Så vårt mål är att inte gå bakåt i den här texten , det vill säga om vi inte matchar, vill vi inte att vår matchning börjar igen från den position som vi började matcha med. För att uppnå detta ska vi leta efter ett efterföljande i vårt mönster precis innan vårt missförhållande inträffade (substring abc ), som också är ett prefix för substring av vårt mönster . För vårt exempel, eftersom alla karaktärer är unika, finns det inget suffix, det är prefixet för vår matchade substring. Så vad det betyder är att vår nästa jämförelse börjar från index 0 . Håll in lite, du förstår varför vi gjorde det här. Därefter jämför vi Text [3] med Mönster [0] och det stämmer inte. Efter det, för Text från index 4 till index 9 och för Mönster från index 0 till index 5 , hittar vi en matchning. Vi finner en missanpassning i text [10] och mönster [6] . Så vi tar substrängen från Mönster direkt före den punkt där missanpassning inträffar (substring abcdabc ), vi kontrollerar efter ett eftertecken, det är också ett prefix för denna substring. Vi kan se här ab är både suffixet och prefixet för denna substring. Vad det betyder är, eftersom vi har matchat till Text [10] , är tecknen precis innan missanpassningen ab . Det vi kan dra slutsatsen är att eftersom ab också är ett prefix för den substring vi tog, behöver vi inte kontrollera ab igen och nästa kontroll kan börja från Text [10] och Mönster [2] . Vi behövde inte titta tillbaka till hela texten , vi kan börja direkt där vårt missförstånd inträffade. Nu kontrollerar vi Text [10] och Mönster [2] , eftersom det är ett missanpassning, och substrängen före missanpassning ( abc ) inte innehåller ett suffix som också är ett prefix, vi kontrollerar Text [10] och Mönster [0] , de matchar inte. Därefter för Text från index 11 till index 17 och för Mönster från index 0 till index 6 . Vi finner ett missförhållande i text [18] och mönster [7] . Så igen kontrollerar vi delsträngen före missanpassning (substring abcdabc ) och finner att abc är både suffixet och prefixet. Så eftersom vi matchade till Mönster [7] , måste abc vara före Text [18] . Det betyder att vi inte behöver jämföra förrän Text [17] och vår jämförelse kommer att börja från Text [18] och Mönster [3] . Således hittar vi en match och vi kommer tillbaka 15 som är vårt startindex för matchen. Så här fungerar vår KMP Substring Search med information om suffix och prefix.
Hur beräknar vi effektivt om suffix är samma som prefix och vid vilken punkt vi börjar kontrollen om det finns ett karaktärsöverensstämmelse mellan text och mönster . Låt oss ta en titt på ett exempel:
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
Vi genererar en matris som innehåller den information som krävs. Låt oss ringa matrisen S. Storleken på matrisen kommer att vara samma som längden på mönstret. Eftersom den första bokstaven i mönstret inte kan vara eftertalet av något prefix, sätter vi S [0] = 0 . Vi tar i = 1 och j = 0 till en början. Vid varje steg jämför vi Mönster [i] och Mönster [j] och steg i . Om det finns en matchning sätter vi S [i] = j + 1 och steget j , om det finns ett fel, kontrollerar vi den tidigare värdepositionen för j (om tillgänglig) och ställer in j = S [j-1] (om j är inte lika med 0 ), vi fortsätter att göra detta tills S [j] inte matchar med S [i] eller j inte blir 0 . För den senare satte vi S [i] = 0 . För vårt exempel:
j i
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
Mönster [j] och Mönster [i] stämmer inte, så vi ökar i och eftersom j är 0 , kontrollerar vi inte det tidigare värdet och sätter Mönster [i] = 0 . Om vi fortsätter att öka i , för i = 4 , får vi en matchning, så vi sätter S [i] = S [4] = j + 1 = 0 + 1 = 1 och steget j och i . Vår matris kommer att se ut:
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 | | | |
+---------+---+---+---+---+---+---+---+---+
Eftersom Mönster [1] och Mönster [5] är en matchning sätter vi S [i] = S [5] = j + 1 = 1 + 1 = 2 . Om vi fortsätter, kommer vi att hitta en missanpassning för j = 3 och i = 7 . Eftersom j inte är lika med 0 sätter vi j = S [j-1] . Och vi ska jämföra karaktärerna i i och j är samma eller inte, eftersom de är samma, lägger vi S [i] = j + 1. Vår slutförda matris kommer att se ut som:
+---------+---+---+---+---+---+---+---+---+
| S | 0 | 0 | 0 | 0 | 1 | 2 | 3 | 1 |
+---------+---+---+---+---+---+---+---+---+
Detta är vår önskade grupp. Här betyder ett icke-nollvärde på S [i] att det finns en S [i] -längd-suffix samma som prefixet i den substring (substring från 0 till i ) och nästa jämförelse kommer att börja från S [i] + 1- positionen för Mönster . Vår algoritm för att generera matrisen skulle se ut:
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
Tidskomplexiteten för att bygga denna grupp är O(n) och rymdkomplexiteten är också O(n) . För att säkerställa att du helt har förstått algoritmen, försök att generera en matris för aabaabaa mönster och kontrollera om resultatet matchar den här .
Låt oss nu göra en substringssökning med följande exempel:
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
| 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 |
+---------+---+---+---+---+---+---+
Vi har en text , ett mönster och en förberäknad matris S med vår logik definierad tidigare. Vi jämför text [0] och mönster [0] och de är samma. Text [1] och Mönster [1] är samma. Text [2] och Mönster [2] är inte samma. Vi kontrollerar värdet på positionen rätt före felanpassningen. Eftersom S [1] är 0 finns det inget suffix som är samma som prefixet i vår substring och vår jämförelse börjar på position S [1] , som är 0 . Så mönster [0] är inte samma som text [2] , så vi fortsätter. Text [3] är samma som Mönster [0] och det finns en matchning till Text [8] och Mönster [5] . Vi går ett steg tillbaka i S- matrisen och hittar 2 . Så detta innebär att det finns ett prefix av längd 2 som också är eftertecknet på denna substring ( abcab) som är ab . Det betyder också att det finns en ab före text [8] . Så vi kan säkert ignorera Mönster [0] och Mönster [1] och starta vår nästa jämförelse från Mönster [2] och Text [8] . Om vi fortsätter hittar vi mönstret i texten . Vår procedur kommer att se ut:
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
Tidskomplexiteten för denna algoritm förutom Suffix Array-beräkningen är O(m) . Eftersom GenerateSuffixArray tar O(n) är den totala tidskomplexiteten för KMP-algoritmen: O(m+n) .
PS: Om du vill hitta flera förekomster av Mönster i texten , istället för att returnera värdet, skriv ut det / lagra det och ställ in j := S[j-1] . Håll också en flag att spåra om du har hittat någon händelse eller inte och hantera den i enlighet därmed.
Pythonimplementering av KMP-algoritm.
Höstack : strängen där ett givet mönster måste sökas.
Nål : Mönstret som ska sökas.
Tidskomplexitet : Sökpartiet (strstr-metoden) har komplexiteten O (n) där n är längden på höstacken, men eftersom nålen också förfördelas för byggnadsprefixtabell O (m) krävs för att bygga prefixtabellen där m är längden på nålen.
Därför är den totala tidskomplexiteten för KMP O (n + m)
Rymdkomplexitet : O (m) på grund av prefixtabellen på nålen.
Obs: Efter implementering returnerar matchningens startposition i höstack (om det finns en matchning) annars returnerar -1, för kantfall som om nål / höstack är en tom sträng eller nål inte hittas i höstacken.
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)