Z-Algorithm

Contents :

• Objective of this post
• An Awesome video tutorial on You Tube
• Implementation in C++
• Practice Problems

---

1. Objective of this post : In problems of string matching or searching we often try to apply library functions like find() in C++ or try to apply brute force, but most of the time we get TLE. Let N = length of the text and M = length of pattern which we need to search in the given text. We got TLE because in these cases our complexity is O(n*m). But we can reduce it to O(n + m) using some efficient string searching algorithms which requires some preprocessing like :
   
   1. KMP String search Algorithm
   2. Z Algorithm
   Z-Algorithm can be used directly or as a subproblem in problems like :
   
   • Find the all the occurrence of a string in the given text.
   • Find the long prefix which is also a suffix.
   • And many more. . .

2. Z-Algorithm with implementation in JAVA

3. Implementation in C++ :

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

   #include<bits/stdc++.h> using namespace std; typedef long long ll; void ZAlgorithm(string text, string pattern){ string s = pattern + "$" + text; int n = s.size(); int Z[n] = {0}; int j = 0, lo, hi; lo = hi = 0; for(int i = 1 ; i < n ; i ++){ if(hi < i){ lo = hi = i; while(hi < n and s[hi - lo] == s[hi]){ hi++; } Z[i] = hi - lo; hi--; }else{ int x = i - lo; if(Z[x] < hi - i + 1){ Z[i] = Z[x]; }else{ lo = i; while(hi < n and s[hi - lo] == s[hi]){ hi++; } Z[i] = hi - lo; hi--; } } } cout << "Pattern found at following indices\n"; for(int i = 0 ; i < n ; i ++){ if(Z[i] == pattern.size()){ cout << i - pattern.size() << endl; } } } int main(){ string text, pattern; cin >> text >> pattern; ZAlgorithm(text, pattern); }

4. Practice Problems :
   Link