Z algorithm in Python

By Karan Mittal

In this tutorial, we’ll be learning about the Z algorithm in Python.

Before looking at the code let’s talk about what exactly the Z algorithm is about. Z algorithm helps us to find out the position of occurrences of a pattern within an input string.

Eg :

input string: aaaaaaa

pattern: aaaa

output: the pattern occurs at positions: 0 1 2 3

Explanation : in the input string the pattern aaaa occurs at (aaaa)aaa,a(aaaa)aa,aa(aaaa)a,aaa(aaaa)

Z algorithm explanation:

1. We first make a new string containing the pattern, a special differentiator symbol, and the input string respectively.,i.e, we concat the 2 strings.
2. Then we take 2 variables to traverse in the 2 parts of the string one traversals the pattern string and the other help in traversing the input string. We then take a counter variable and an empty list.
3. We first check if any character is equivalent to the first character of the pattern string if a match is foraged or found then we increment the value of count variable and shift to the next character in both the input string and pattern string and check for the same. this process is followed until the characters don’t match.
4. When the characters don’t match we append the value of count to the empty list, make the count value zero, the index of pattern string zero and then shift the index of the input string to the next character.
5. We repeat this process until we traverse the entire input string

This is the Z algorithm!

The following is the Python code regarding the Z algorithm with time complexity of O(n)

n=input()#input string
pat=input()#pattern
joinn=pat+'$'+n #combination of both the strings
coun=0
i=0
j=1
z=[]

while(j<len(joinn)):
    
    if(joinn[i]==joinn[j]):#comparing each element with every other element
        coun+=1
        j+=1
        i+=1
        continue
    else:
        z.append(coun)
        coun=0
        j-=i
        i=0
        
    j+=1

if(joinn[j-len(pat):]==pat):#checking for the last substring of size of pattern
    z.append(len(pat))

print ("the occurences of pattern is at positions: ",end=' ')
for i in range(len(z)):
    if(z[i]==len(pat)):
        print(i-len(pat),end=' ')
#code by
#karan mittal

    
        
        

Hope this code helped you with your doubts regarding Z algorithm.

If you have any issues with the code you can write down your queries in the comments box below.

Happy Coding.

Also read: Array Rotation using Reversal Algorithm in Python