algorithm
पदार्थ खोज
खोज…
सीएमपी में केएमपी एल्गोरिदम
एक पाठ txt और एक पैटर्न पैट को देखते हुए, इस कार्यक्रम का उद्देश्य txt में पैट के सभी संभावना को प्रिंट करना होगा।
उदाहरण:
इनपुट:
txt[] = "THIS IS A TEST TEXT"
pat[] = "TEST"
उत्पादन:
Pattern found at index 10
इनपुट:
txt[] = "AABAACAADAABAAABAA"
pat[] = "AABA"
उत्पादन:
Pattern found at index 0
Pattern found at index 9
Pattern found at index 13
सी भाषा कार्यान्वयन:
// 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;
}
आउटपुट:
Found pattern at index 10
संदर्भ:
http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/
राबिन-कार्प एल्गोरिथ्म का परिचय
राबिन-कार्प एल्गोरिथ्म रिचर्ड एम। कार्प और माइकल ओ। राबिन द्वारा बनाया गया एक स्ट्रिंग खोज एल्गोरिथ्म है जो किसी पाठ में पैटर्न स्ट्रिंग्स के सेट में से किसी एक को खोजने के लिए हैशिंग का उपयोग करता है।
एक स्ट्रिंग की सबस्ट्रिंग अन्य स्ट्रिंग है कि में होता है। उदाहरण के लिए, ver stackoverflow की सबस्ट्रिंग है। परवर्ती के साथ भ्रमित नहीं होना क्योंकि आवरण उसी तार का एक अनुवर्ती है। दूसरे शब्दों में, किसी स्ट्रिंग में लगातार अक्षरों का कोई सबसेट दिए गए स्ट्रिंग का एक विकल्प है।
राबिन-कार्प एल्गोरिथ्म में, हम अपने पैटर्न का एक हैश उत्पन्न करेंगे, जिसे हम देख रहे हैं और जांच रहे हैं कि हमारे टेक्स्ट का रोलिंग हैश पैटर्न से मेल खाता है या नहीं। यदि यह मेल नहीं खाता है, तो हम गारंटी दे सकते हैं कि पाठ में पैटर्न मौजूद नहीं है । हालांकि, अगर यह मेल खाता है, तो पैटर्न पाठ में मौजूद हो सकता है। आइए एक उदाहरण देखें:
मान लें कि हमारे पास एक पाठ है: yeminsajid और हम यह पता लगाना चाहते हैं कि क्या पाठ में पैटर्न nsa मौजूद है। हैश और रोलिंग हैश की गणना करने के लिए, हमें एक अभाज्य संख्या का उपयोग करना होगा। यह कोई भी अभाज्य संख्या हो सकती है। इस उदाहरण के लिए प्राइम = 11 लेते हैं। हम इस सूत्र का उपयोग करके हैश मान निर्धारित करेंगे:
(1st letter) X (prime) + (2nd letter) X (prime)¹ + (3rd letter) X (prime)² X + ......
हम निरूपित करेंगे:
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
Nsa का हैश मान होगा:
14 X 11⁰ + 19 X 11¹ + 1 X 11² = 344
अब हम अपने टेक्स्ट का रोलिंग-हैश ढूंढते हैं। यदि रोलिंग हैश हमारे पैटर्न के हैश मान के साथ मेल खाता है, तो हम जांच करेंगे कि तार मेल खाते हैं या नहीं। चूँकि हमारे पैटर्न में 3 अक्षर हैं, हम अपने पाठ से 1 3 अक्षर yem लेंगे और हैश मान की गणना करेंगे। हमें मिला:
25 X 11⁰ + 5 X 11¹ + 13 X 11² = 1653
यह मान हमारे पैटर्न के हैश मान से मेल नहीं खाता है। तो स्ट्रिंग यहाँ मौजूद नहीं है। अब हमें अगले कदम पर विचार करने की आवश्यकता है। हमारे अगले स्ट्रिंग ईएमआई के हैश मान की गणना करने के लिए। हम अपने सूत्र का उपयोग करके इसकी गणना कर सकते हैं। लेकिन यह बल्कि तुच्छ होगा और हमें अधिक लागत आएगी। इसके बजाय, हम एक और तकनीक का उपयोग करते हैं।
- हम अपने वर्तमान हैश मान से पिछले स्ट्रिंग के पहले अक्षर के मूल्य को घटाते हैं। इस मामले में, वाई । हमें मिलता है,
1653 - 25 = 1628। - हम अपने प्राइम के साथ अंतर को विभाजित करते हैं, जो इस उदाहरण के लिए 11 है । हमें मिलता है,
1628 / 11 = 148। - हम नए अक्षर X (अभियोक्ता) को जोड़ते हैं , जहाँ m भाग की लंबाई भागफल के साथ होती है, जो कि i = 9 है । हमें मिलता है,
148 + 9 X 11² = 1237।
नया हैश मान हमारे पैटर्न हैश मान के बराबर नहीं है। आगे बढ़ते हुए, n के लिए हम मिलते हैं:
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
यह मेल नहीं खाता। उसके बाद, एस के लिए , हमें मिलता है:
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
यह मेल नहीं खाता। अगला, एक के लिए , हमें मिलता है:
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
यह एक मेल है! अब हम अपने पैटर्न की वर्तमान स्ट्रिंग से तुलना करते हैं। चूंकि दोनों तार मेल खाते हैं, इसलिए स्ट्रिंग में विकल्प मौजूद है। और हम अपने प्रतिस्थापन की प्रारंभिक स्थिति लौटाते हैं।
छद्म कोड होगा:
हैश गणना:
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
हैश पुनर्गणना:
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
स्ट्रिंग मैच:
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
राबिन-कार्प:
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
यदि एल्गोरिथ्म को कोई मैच नहीं मिलता है, तो यह केवल -1 देता है।
इस एल्गोरिथ्म का उपयोग साहित्यिक चोरी का पता लगाने में किया जाता है। स्रोत सामग्री को देखते हुए, एल्गोरिथ्म तेजी से स्रोत सामग्री से वाक्यों के उदाहरणों के लिए एक पेपर के माध्यम से खोज सकता है, मामले और विराम चिह्न जैसे विवरणों की अनदेखी कर सकता है। मांगे गए तारों की बहुतायत के कारण, एकल-स्ट्रिंग खोज एल्गोरिदम यहां अव्यवहारिक हैं। फिर से, नूथ-मॉरिस-प्रैट एल्गोरिथ्म या बोयर-मूर स्ट्रिंग सर्च एल्गोरिथ्म राबिन-कार्प की तुलना में तेजी से एकल पैटर्न स्ट्रिंग खोज एल्गोरिथ्म है। हालांकि, यह कई पैटर्न खोज के लिए पसंद का एल्गोरिथ्म है। यदि हम बड़ी संख्या में से किसी को खोजना चाहते हैं, तो एक पाठ में कश्मीर, निश्चित लंबाई पैटर्न कहें, हम राबिन-कार्प एल्गोरिथ्म का एक सरल संस्करण बना सकते हैं।
संयुक्त लंबाई m के लंबाई n और p पैटर्न के पाठ के लिए, इसका औसत और सबसे अच्छा मामला चलने का समय O (n + m) अंतरिक्ष O (p) में है , लेकिन इसका सबसे खराब समय O (nm) है ।
नॉट-मॉरिस-प्रैट (केएमपी) एल्गोरिदम का परिचय
मान लीजिए कि हमारे पास एक पाठ और एक पैटर्न है । हमें यह निर्धारित करने की आवश्यकता है कि पाठ में पैटर्न मौजूद है या नहीं। उदाहरण के लिए:
+-------+---+---+---+---+---+---+---+---+
| 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 |
+---------+---+---+---+---+
यह पैटर्न पाठ में मौजूद है। तो हमारी प्रतिस्थापन खोज को 3 वापस करना चाहिए, उस स्थिति का सूचकांक जिसमें से यह पैटर्न शुरू होता है। तो हमारी ब्रूट फोर्स सबस्टेशन खोज प्रक्रिया को कैसे काम करती है?
क्या हम आम तौर पर करते हैं: हम पाठ और हमारे * पैटर्न के 0 सूचकांक के 0 सूचकांक से शुरू करते हैं और हम पैटर्न [0] के साथ पाठ [0] की तुलना करें। चूंकि वे एक मैच नहीं हैं, हम अपने पाठ के अगले इंडेक्स पर जाते हैं और हम पैटर्न [0] के साथ पाठ [1] की तुलना करते हैं। चूंकि यह एक मैच है, हम अपने पैटर्न के सूचकांक और पाठ के सूचकांक को भी बढ़ाते हैं। हम पैटर्न [1] के साथ पाठ [2] की तुलना करते हैं। वे एक मैच भी हैं। पहले बताई गई इसी प्रक्रिया का अनुसरण करते हुए, अब हम पैटर्न [2] के साथ पाठ [3] की तुलना करते हैं। जैसा कि वे मैच नहीं करते हैं, हम अगले स्थान से शुरू करते हैं जहां हमने मैच ढूंढना शुरू किया। यह पाठ का अनुक्रमणिका 2 है। हम पैटर्न [0] के साथ पाठ [2] की तुलना करते हैं। वे मेल नहीं खाते। फिर पाठ के सूचकांक में वृद्धि, हम पाठ की तुलना [3] पैटर्न [0] से करते हैं । उनका मिलान होता है। दोबारा टेक्स्ट [4] और पैटर्न [1] मैच, टेक्स्ट [5] और पैटर्न [2] मैच और टेक्स्ट [6] और पैटर्न [3] मैच। चूँकि हम अपने पैटर्न के अंत तक पहुँच चुके हैं, अब हम उस इंडेक्स को लौटा देते हैं जिससे हमारा मैच शुरू हुआ, वह 3 है । यदि हमारा पैटर्न था: bcgll , इसका मतलब है कि यदि पैटर्न हमारे पाठ में मौजूद नहीं था, तो हमारी खोज को अपवाद या -1 या किसी अन्य पूर्वनिर्धारित मूल्य पर वापस लौटना चाहिए। हम स्पष्ट रूप से देख सकते हैं कि, सबसे खराब स्थिति में, यह एल्गोरिथ्म O(mn) समय लेगा जहाँ m पाठ की लंबाई और n पैटर्न की लंबाई है। हम इस समय की जटिलता को कैसे कम करते हैं? यह वह जगह है जहाँ केएमपी सब्स्टीट्यूट सर्च एल्गोरिथम चित्र में आता है।
नथ-मॉरिस-प्रैट स्ट्रिंग सर्चिंग एलगोरिदम या केएमपी एल्गोरिथ्म एक "पैटर्न" की घटनाओं के लिए खोज करता है एक मुख्य "टेक्स्ट" के अवलोकन के नियोजन के द्वारा कि जब कोई बेमेल होता है, तो शब्द ही यह निर्धारित करने के लिए पर्याप्त जानकारी का प्रतीक है कि अगला मैच कहां से शुरू हो सकता है। , इस प्रकार पहले से मिलान किए गए पात्रों की पुन: परीक्षा को दरकिनार कर देता है। इस एल्गोरिथ्म की कल्पना 1970 में डोनल्ड नूथ और वॉन प्रैट ने की थी और स्वतंत्र रूप से जेम्स एच। मॉरिस ने की थी । तीनों ने 1977 में इसे संयुक्त रूप से प्रकाशित किया।
आइए बेहतर समझने के लिए हमारे उदाहरण पाठ और पैटर्न का विस्तार करें:
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 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 |
+---------+---+---+---+---+---+---+---+---+
सबसे पहले, हमारे पाठ और पैटर्न सूचकांक 2 तक मेल खाते हैं। पाठ [3] और पैटर्न [३] मेल नहीं खाते। इसलिए हमारा उद्देश्य इस पाठ में पीछे की ओर नहीं जाना है, अर्थात्, एक बेमेल के मामले में, हम नहीं चाहते कि हमारा मिलान फिर से उस स्थिति से शुरू हो जाए, जिसके साथ हमने मिलान करना शुरू किया था। इसे प्राप्त करने के लिए, हम अपने बेमेल होने से पहले अपने पैटर्न में एक प्रत्यय की तलाश करेंगे ( एबीसी को प्रतिस्थापित करना ), जो कि हमारे पैटर्न के विकल्प का एक उपसर्ग भी है। हमारे उदाहरण के लिए, चूंकि सभी वर्ण अद्वितीय हैं, कोई प्रत्यय नहीं है, यह हमारे मिलान किए गए प्रतिस्थापन का उपसर्ग है। तो इसका मतलब क्या है, हमारी अगली तुलना इंडेक्स 0 से शुरू होगी। थोडा रुको, तुम समझ जाओगे कि हमने ऐसा क्यों किया। अगला, हम पैटर्न [0] के साथ पाठ [3] की तुलना करते हैं और यह मेल नहीं खाता। उसके बाद, सूचकांक 4 से सूचकांक 9 और सूचकांक से 5 सूचकांक 0 से पैटर्न के लिए पाठ के लिए, हमें कोई मेल मिलता। हम पाठ [10] और पैटर्न [6] में एक बेमेल पाते हैं। तो हम उस बिंदु से ठीक पहले पैटर्न से सबस्ट्रिंग लेते हैं, जहां बेमेल घटित होता है ( एब्सकॉर्डिंग को दबाते हुए ), हम एक प्रत्यय की जांच करते हैं, यह भी इस सबस्ट्रिंग का एक उपसर्ग है। हम देख सकते हैं कि एब इस प्रतिस्थापन के प्रत्यय और उपसर्ग दोनों है। के बाद से हम सही से पहले बेमेल अब है जब तक पाठ [10] मिलान कर लेते हैं, वर्ण, क्या है कि साधन है। हम जो अनुमान लगा सकते हैं वह यह है कि चूंकि एब हमारे द्वारा लिए गए सबस्ट्रिंग का एक उपसर्ग है, इसलिए हमें एब को फिर से जांचना नहीं पड़ता है और अगला चेक टेक्स्ट [10] और पैटर्न [2] से शुरू हो सकता है। हमें पूरे पाठ को वापस नहीं देखना पड़ा, हम सीधे वहीं से शुरू कर सकते हैं जहाँ हमारा बेमेल विवाह हुआ था। अब हम टेक्स्ट [10] और पैटर्न [2] की जांच करते हैं , क्योंकि यह एक बेमेल है, और मिसमैच ( abc ) से पहले विकल्प में एक प्रत्यय नहीं होता है, जो एक उपसर्ग भी है, हम टेक्स्ट [10] और पैटर्न की जाँच करते हैं [0] , वे मेल नहीं खाते। उसके बाद अनुक्रमणिका 11 से सूचकांक 17 तक और अनुक्रमणिका 0 से अनुक्रमणिका 6 तक प्रतिमान के लिए पाठ । हम पाठ [18] और पैटर्न [7] में एक बेमेल पाते हैं। तो फिर से हम मिसमैच से पहले सबस्ट्रिंग की जाँच करते हैं ( एब्सकॉर्डिंग एबीसीबीबीसी ) और पाते हैं कि एबीसी प्रत्यय और उपसर्ग दोनों है। इसलिए जब से हमने पैटर्न [7] तक मिलान किया, abc को टेक्स्ट [18] से पहले होना चाहिए। इसका मतलब है, हमें पाठ [17] तक तुलना करने की आवश्यकता नहीं है और हमारी तुलना पाठ [18] और पैटर्न [3] से शुरू होगी। इस प्रकार हमें एक मैच मिलेगा और हम 15 वापसी करेंगे जो कि मैच का हमारा शुरुआती सूचकांक है। प्रत्यय और उपसर्ग की जानकारी का उपयोग करके हमारा KMP सब्स्टीट्यूट सर्च काम करता है।
अब, यदि प्रत्यय उपसर्ग के समान है और पाठ और पैटर्न के बीच वर्ण का बेमेल है तो चेक को शुरू करने के लिए किस बिंदु पर हम कुशलतापूर्वक गणना करते हैं। आइए एक उदाहरण देखें:
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
हम एक सरणी उत्पन्न करेंगे जिसमें आवश्यक जानकारी होगी। चलो सरणी एस को बुलाओ। सरणी का आकार पैटर्न की लंबाई के समान होगा। चूंकि पैटर्न का पहला अक्षर किसी भी उपसर्ग का प्रत्यय नहीं हो सकता है, हम S [0] = 0 डाल देंगे। हम पहली बार में i = 1 और j = 0 लेते हैं। प्रत्येक चरण में हम पैटर्न [i] और पैटर्न [j] और वेतन वृद्धि i की तुलना करते हैं । यदि कोई मैच होता है तो हम S [i] = j + 1 और वेतन वृद्धि j , यदि कोई मिसमैच होता है, तो हम j के पिछले मान की स्थिति (यदि उपलब्ध हो) और सेट j = S [j-1] (यदि j 0 के बराबर नहीं है), हम इसे तब तक करते रहते हैं जब तक S [j] S [i] से मेल नहीं खाता या j 0 नहीं बन जाता। बाद के एक के लिए, हम S [i] = 0 डालते हैं। हमारे उदाहरण के लिए:
j i
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
पैटर्न [j] और पैटर्न [i] मेल नहीं खाते हैं, इसलिए हम i को बढ़ाते हैं और क्योंकि j 0 है , हम पिछले मान की जांच नहीं करते हैं और पैटर्न [i] = 0 डालते हैं। अगर हम मैं incrementing, मैं = 4 रखने के लिए, हम एक मैच है, तो हम एस डाल = मिलेगा [i] एस [4] = j + 1 = 0 + 1 = 1 और वेतन वृद्धि j और मैं। हमारे सरणी की तरह दिखेगा:
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 | | | |
+---------+---+---+---+---+---+---+---+---+
चूंकि पैटर्न [1] और पैटर्न [5] एक मेल है, इसलिए हमने S [i] = S [5] = j + १ = १ + १ = २ डाला। यदि हम जारी रखते हैं, तो हम j = 3 और i = 7 के लिए एक बेमेल पाएंगे। चूँकि j 0 के बराबर नहीं है, इसलिए हमने j = S [j-1] डाल दिया। और हम अक्षर की तुलना करेंगे i और j समान हैं या नहीं, क्योंकि वे समान हैं, हम S [i] = j + 1. डालेंगे। हमारी पूर्ण सारणी इस तरह दिखाई देगी:
+---------+---+---+---+---+---+---+---+---+
| S | 0 | 0 | 0 | 0 | 1 | 2 | 3 | 1 |
+---------+---+---+---+---+---+---+---+---+
यह हमारी आवश्यक सरणी है। यहाँ S [i] का एक नॉनज़रो-वैल्यू मतलब है कि एस (i) लंबाई में प्रत्यय के समान है जो कि सबस्ट्रिंग में उपसर्ग ( 0 से i के बीच में है ) और अगली तुलना S से शुरू होगी [i] + 1 स्थिति पैटर्न । सरणी उत्पन्न करने के लिए हमारा एल्गोरिथम ऐसा दिखेगा:
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
इस सरणी को बनाने की समय जटिलता O(n) और अंतरिक्ष जटिलता O(n) । यह सुनिश्चित करने के लिए कि यदि आपने एल्गोरिथ्म को पूरी तरह से समझ लिया है, तो पैटर्न aabaabaa लिए एक सरणी उत्पन्न करने की कोशिश करें और जांचें कि क्या परिणाम इस एक के साथ मेल खाता है।
अब निम्नलिखित उदाहरण का उपयोग करते हुए एक विकल्प खोज करते हैं:
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
| 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 |
+---------+---+---+---+---+---+---+
हमारे पास पहले से परिभाषित हमारे तर्क का उपयोग करके एक पाठ , एक पैटर्न और एक पूर्व-गणना की गई सरणी एस है । हम पाठ [0] और पैटर्न [0] की तुलना करते हैं और वे समान हैं। पाठ [1] और पैटर्न [१] समान हैं। पाठ [2] और पैटर्न [२] समान नहीं हैं। हम बेमेल से ठीक पहले की स्थिति पर मूल्य की जांच करते हैं। चूँकि S [1] 0 है , इसलिए कोई भी प्रत्यय नहीं है जो हमारे विकल्प में उपसर्ग के समान है और हमारी तुलना S [1] से शुरू होती है, जो कि 0 है । इसलिए पैटर्न [0] टेक्स्ट [2] के समान नहीं है, इसलिए हम आगे बढ़ते हैं। पाठ [3] पैटर्न [0] के समान है और पाठ [8] और पैटर्न [५] तक मेल है। हम एस सरणी में एक कदम पीछे जाते हैं और 2 पाते हैं। तो इसका मतलब है कि लंबाई 2 का एक उपसर्ग है जो इस एब्रीडिंग ( abcab) का प्रत्यय है जो ab है । इसका मतलब यह भी है कि पाठ [8] से पहले एक एब है । इसलिए हम सुरक्षित रूप से पैटर्न [0] और पैटर्न [1] को अनदेखा कर सकते हैं और पैटर्न [2] और टेक्स्ट [8] से अपनी अगली तुलना शुरू कर सकते हैं। यदि हम जारी रखते हैं, तो हमें पाठ में पैटर्न मिलेगा। हमारी प्रक्रिया इस तरह दिखाई देगी:
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
इस एल्गोरिथ्म का समय जटिलता प्रत्यय सरणी गणना O(m) । चूंकि GenerateSuffixArray O(n) लेता है, KMP एल्गोरिथम की कुल समय जटिलता है: O(m+n) ।
पुनश्च: यदि आप पाठ में पैटर्न की कई घटनाओं को खोजना चाहते हैं, तो मूल्य को वापस करने के बजाय, इसे प्रिंट करें / स्टोर करें और j := S[j-1] । यह भी पता लगाने के लिए एक flag रखें कि क्या आपको कोई घटना मिली है या नहीं और उसी के अनुसार इसे संभालें।
केएमपी एल्गोरिथ्म के पायथन कार्यान्वयन।
हेडस्टैक : वह स्ट्रिंग जिसमें दिए गए पैटर्न को खोजना पड़ता है।
सुई : खोजा जाने वाला पैटर्न।
समय की जटिलता : खोज भाग (स्ट्रैस विधि) में जटिलता हे (n) है जहां n , हाईस्टैक की लंबाई है, लेकिन सुई उपसर्ग तालिका के निर्माण के लिए सुई भी पूर्व की है। उपसर्ग तालिका के निर्माण के लिए O (m) आवश्यक है जहां m की लंबाई है सुई।
इसलिए, KMP के लिए समग्र समय जटिलता O (n + m) है
अंतरिक्ष जटिलता : सुई पर उपसर्ग तालिका के कारण ओ (एम) ।
नोट: निम्नलिखित कार्यान्वयन हैस्टैक में मैच की शुरुआत की स्थिति देता है (यदि कोई मैच है) तो रिटर्न -1, जैसे किनारे के मामलों के लिए अगर सुई / हैस्टैक एक खाली स्ट्रिंग है या सुई हैस्टैक में नहीं पाई जाती है।
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)
