1 month, 2 weeks

Z Algorithm




Z algorithm is an algorithm for searching a given pattern in a string, which is an efficient algorithm as it has linear time complexity. It has a time complexity of O(m+n), where m is the length of the string and n is the length of the pattern to be searched.

If we had a method of computing the Z function quickly, then we can solve the string matching problem as well by computing the Z function for the string P$T and walking over the array, where ‘$’ is a special character that does not occur in P or T.


The Naïve Algorithm
A Simple Solution is to run two nested loops, the outer loop goes to every index and the inner loop finds length of the longest prefix that matches the substring starting at the current index. The time complexity of this solution is O(n^2).

def z_naive(s):                                                                                                   
    Z = [len(s)]                                                                                                     
    for k in range(1, len(s)):                                                                                 
        n = 0                                                                                                           
        while n + k < len(s) and s[n] == s[n + k]:                                                    
            n += 1                                                                                                     
        Z.append(n)                                                                                                
    return Z                                                                                                           

or Python magic:

from itertools import takewhile    #takewhile(predicate, iterable)

#The predicate is either a built-in function or a user-defined function. It can be even lambda functions.


Z = [len(list(takewhile(lambda p: p[0] == p[1], zip(s, s[k:])))) for k in range(len(s))]

The function takewhile() takes a predicate and an iterable as arguments. The iterable is iterated to check each of its elements. If the elements on the specified predicate, evaluates to true, it is returned. Otherwise, the loop is terminated.

The naïve implementation has O(|s|^2) time complexity, where |s| is the length of the string. (Quadratic Time Complexity)

 

How to build Z array                                                         

String: b a a b a a                                                                                 
Pattern:  a a b                                                                                       
New Text : a a b $ b a a b a a                                                               

First thing we will do is to generate a new string by concatenating the old strings. So the new string becomes aab$baabaa. Now we will generate the Z array for the this string:

 

Index 0 1 2 3 4 5 6 7 8 10
Text a a b $ b a a b a a
Z Value x 1 0 0 0 3 1 0 2 1


a. Substring should start from ith position.                                                                     

b. substring should be of maximum length which is also a prefix                                  

1. At index 0:
Finding substring from i(0th index) till end which is also prefix of given text.

a a b $ b a a b a a => of length 10 is the longest substring which is also a prefix of the text. But this will not help in pattern matching so we make it as x in Z array.

2. At index 1:
Finding longest substring starting from position 1 till end which is also a prefix of the text.

such substring are:

a. "a" => prefix of the text "a a b $ b a a b a a" and length is 1.                                         

b. "a b" => Not a prefix                                                                            

c. "a b $" => Not a prefix                                      

d. "a b $ b" => Not a prefix                                                   

e. "a b $ b a" => Not a prefix                                                            

and so...                                                                                        

Here the only longest substring which is also a prefix is "a" and its length is 1. It is stored in Z array.

3. At index 2:
Substrings are:                                                             

a. "b" => Not a prefix                                           

b. "b $" => Not a prefix                                       

c. "b $ b" => Not a prefix                                                             

and so...                                                                              

Here there is no substring which is also a prefix of text T. So we are storing zero at index 2 in Z array.

4. At index 5:
substrings are:

a. "a" => prefix of text "a a b $ b a a b a a" and length is 1.                     

b. "a a" => prefix of text "a a b $ b a a b a a" and length is 2.

c. "a a b" => prefix of text "a a b $ b a a b a a" and length is 3.                     

d. "a a b a"=> Not a prefix                                                                                                 

and so...                                                                                


Here the longest substring which is also a prefix of text T is "a a b" of length 3. So we store 3 at index 5 in Z array. Finally, If any value in Z array is the same as the length of the pattern then that pattern is present in the text T.


The idea is to maintain an interval [L, R] which is the interval with max R such that [L,R] is prefix substring (substring which is also prefix). 

Steps for maintaining this interval are as follows – 

1) If i > R then there is no prefix substring that starts before i and ends after i, so we reset L and R and compute new [L,R] by comparing   str[0..] to str[i..] and get Z[i] (= R-L+1).

2) If i <= R then let K = i-L,  now Z[i] >= min(Z[K], R-i+1)  because str[i..] matches with str[K..] for at least R-i+1 characters (they are in    [L,R] interval which we know is a prefix substring).     
   Now two sub-cases arise – 
      a) If Z[K] < R-i+1  then there is no prefix substring starting at str[i] (otherwise Z[K] would be larger)  so  Z[i] = Z[K]  and   interval [L,R] remains same.
      b) If Z[K] >= R-i+1 then it is possible to extend the [L,R] interval thus we will set L as i and start matching from str[R]  onwards  and get new R then we will update interval [L,R] and calculate Z[i] (=R-L+1).


# Fills Z array for given string str[]
def get_Zarr(string, z):                                                                      
       n = len(string)                                                                            
      # [L,R] make a window which matches                                      
      # with prefix of s                                                                          
       left, right, k = 0, 0, 0                                                                   

       for i in range(1, n):                                                                     
        # if i>R nothing matches so we will calculate.                         
        # Z[i] using naive way.                                                             
            if i > right:                                                                              
                left, right = i, i                                                                      
            # R-L = 0 in starting, so it will start                                         
            # checking from 0'th index.                                                   
                while right < n and string[right - left] == string[right]:         
                    right += 1                                                                       
                z[i] = right - left                                                                  
                right -= 1                                                                           
            else:                                                                                      
            # k = i-L so k corresponds to number which                         
            # matches in [L,R] interval.                                                   
               k = i - left                                                                           
            # if Z[k] is less than remaining interval                                
            # then Z[i] will be equal to Z[k].                                           
                if z[k] < right - i + 1:                                                        
                    z[i] = z[k]                                                                     
                else:                                                                               
                # else start from R and check manually                        
                    left = i                                                                       
                    while right < n and string[right - left] == string[right]:
                        right += 1                                                              
                    z[i] = right - left                                                         
                    right -= 1                                                                   
# prints all occurrences of pattern
# in text using Z algorithm
def find(text, pattern):                                                                   
    # Create concatenated string "P$T"                                         
       concat = pattern + "$" + text                                                  
       left = len(concat)                                                                   
    # Construct Z array                                                                 
       z = [0] * left                                                                           
    get_Zarr(concat, z)                                                                  
    # now looping through Z array for matching condition            
      for i in range(left):                                                                  
        # if Z[i] (matched region) is equal to pattern                       
        # length we got the pattern                                                
          if z[i] == len(pattern):                                                       
              print("Pattern found at index", i - len(pattern) - 1)        

 

Applications of Z Algorithm
- Z Algorithm has an important application in finding DNA patterns in a DNA sequence. It is used in this case because Z algorithm works in linear time and as DNA sequences are very large, Z algorithm works efficiently.
- Z algorithm can also be used to find all occurrences of a word in a sentence.
- Z algorithm can be used anywhere to find a pattern in a string.


Responses(0)







Related