Z एल्गोरिदम

इस एल्गोरिदम का नाम Z एल्गोरिदम है क्योंकि, इस एल्गोरिदम में, हमें एक Z ऐरे बनाने की आवश्यकता होती है। Z ऐरे का आकार टेक्स्ट के आकार के समान होता है। इस ऐरे का उपयोग मुख्य स्ट्रिंग के वर्तमान कैरेक्टर से शुरू होने वाले सबसे लंबे संभावित सबस्ट्रिंग की लंबाई स्टोर करने के लिए किया जाता है। सबसे पहले, पैटर्न और मुख्य टेक्स्ट को एक विशेष सिम्बल के साथ जोड़ा जाता है जो टेक्स्ट और पैटर्न में मौजूद नहीं होता। यदि P पैटर्न है और T मुख्य टेक्स्ट है, तो जोड़ने के बाद, यह P$T होगा (यह मानते हुए कि $ P और T में मौजूद नहीं है)।

इस एल्गोरिदम के लिए, समय जटिलता O(m+n) है क्योंकि m पैटर्न की लंबाई है और n मुख्य स्ट्रिंग की लंबाई है।

इनपुट और आउटपुट

इनपुट: मुख्य स्ट्रिंग: "ABAAABCDBBABCDDEBCABC", पैटर्न: "ABC" आउटपुट: पैटर्न स्थान पर मिला: 4 पैटर्न स्थान पर मिला: 10 पैटर्न स्थान पर मिला: 18

एल्गोरिदम

fillZArray(conStr, ZArray)

इनपुट - conStr पैटर्न और मुख्य टेक्स्ट का जोड़ा हुआ स्ट्रिंग है। ZArray सबसे लंबे संभावित सबस्ट्रिंग के इंडेक्स स्टोर करने के लिए

आउटपुट - भरा हुआ ZArray

Begin 
  n := length of conStr 
  windLeft := 0 and windRight := 0 
  for i := 1 to n, do 
    if i > windRight, then 
      windLeft := i and windRight := i 
      while windRight < n AND conStr[windRight-windLeft] = conStr[windRight], do 
        increase windRight by 1 
      done 
      ZArray[i] := windRight – windLeft 
      decrease windRight by 1 
    else 
      k := i – windLeft 
      if ZArray[k] < windRight – i +1, then 
        ZArray[i] := ZArray[k] 
      else 
        windLeft := i 
        while windRight < n AND conStr[windRight-windLeft] = conStr[windRight], do 
          increase windRight by 1 
        done 
        ZArray[i] := windRight – windLeft 
        decrease windRight by 1 
  done 
End

zAlgorithm(text, pattern)

इनपुट - मुख्य टेक्स्ट और खोजने के लिए पैटर्न

आउटपुट - वह स्थान जहां पैटर्न मिला

Begin 
  conStr = concatenate pattern + "$" + text 
  patLen := length of pattern 
  len := conStr length 
  fillZArray(conStr, ZArray) 
  for i := 0 to len – 1, do 
    if ZArray[i] = patLen, then 
      print the location i – patLen – 1 
  done 
End

उदाहरण

#include<iostream> using namespace std; void fillZArray(string conStr, int zArr[]) { int n = conStr.size(); int windLeft, windRight, k; windLeft = windRight = 0; //initially window size is 0 for(int i = 1; i < n; i++) { if(i > windRight) { windLeft = windRight = i; //window size is 0 but position to i while(windRight < n && conStr[windRight-windLeft] == conStr[windRight]) { windRight++; //extend the right bound of window } zArr[i] = windRight-windLeft; windRight--; }else { k = i-windLeft; if(zArr[k] < windRight-i+1) zArr[i] = zArr[k]; //when kth item less than remaining interval else { windLeft = i; while(windRight < n && conStr[windRight - windLeft] == conStr[windRight]) { windRight++; } zArr[i] = windRight - windLeft; windRight--; } } } } void zAlgorithm(string mainString, string pattern, int array[], int *index) { string concatedStr = pattern + "$" + mainString; //concat with special character int patLen = pattern.size(); int len = concatedStr.size(); int zArr[len]; fillZArray(concatedStr, zArr); for(int i = 0; i

आउटपुट
Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18