Z Algorithm

Hard
0/120
Average time to solve is 15m
profile
Contributed by
31 upvotes
Asked in companies
BarclaysFlipkart limited

Problem statement

You’re given a string S of length N and a string P of length M. Your task is to find the number of occurrences of P in S in linear time.

For example: 
If S = "ababa", and P = "ab", then "ab" occurs twice in "ababa".
Note: 
The string only consists of lowercase English alphabets.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains T, the number of test cases.

The first line of each test case contains two integers N and M, the length of string S and P respectively.

The second line of each test case contains the string S.

The third line of each test case contains the string P.
Output Format: 
The only line of output of each test case should contain an integer denoting the number of occurrences of P in S.
Note: 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
1 <= N, M <= 10^4

Time Limit: 1 sec
Sample Input 1:
2
5 2
ababa
ab
4 10
codercodes
code
Sample Output 1:
2
2
Explanation of Sample Input 1:
In the 1st testcase,
"ab" occurs two times in "ababa". The first occurrence is from position 1 to position 2 and the second occurrence is from position 4 to position 5.

In the 2nd testcase, 
"code" occurs two times in "codercodes". The first occurrence is from position 1 to position 4 and the second occurrence is from position 6 to position 9.
Sample Input 2:
2
7 3
aababba
aba
6 2
zzzzyz
zz
Sample Output 2:
1
3
Hint

Brute Force

Approaches (2)
Brute Force Approach

A basic approach is to check all substrings of string ‘S’ and see if that substring is equal to ‘P’ or not. Let’s see how we’ll do this.

 

  • Initialize an integer variable count = 0.
  • Start by running an outer loop(loop variable i) from 0 to N - M.
  • Then run a nested loop(loop variable j) from 0 to 'M'.
  • For index ‘i’, check if S[i + j] != P[j], if this condition is true, we simply break the inner loop and move to the next i. We do this to check every substring of length ‘M’ if it is equal to 'P' or not.
  • Later on, we check if ‘j’ is equal to 'M' or not, if this condition is true, we increment our count by 1 because we have found a substring of length M which is equal to 'P'.
  • Finally, we return the count which is our final answer.

 

For example-  String S = ababa and String P = ab

Here N = 5 and M = 2

 

  • We first run a loop from 0 to 3(N - M) with loop variable ‘i’.
  • In this loop, we run another loop with a loop variable ‘j’. First, we see if S[i + j] = P[j] or not, and since it is true(S[0] = P[0]), we move to the next ‘j’ and check if S[1] = P[1] or not and since it is also true we move further.
  • But now on moving further ‘j’ becomes 2 and we exit this inner loop but we see that since j == M(2), we increment our count by 1. Now we move further to our next ‘i’ and see if S[1 + 0] = P[0] or not and since this condition doesn’t hold true, we simply break the inner loop and move further and see if S[2 + 0] = P[0] is true or not and this is true since both the characters are ‘a’, then we check if S[2 + 1] = P[1] and again we see that this condition is true and again j = 2 and we increment our count once again by 1.
  • Now for the last ‘i’ we check if S[3 + 0] = P[0] or not and since this condition isn’t true we come out of this nested loop. We also see that the outer loop variable has also reached N - M(3), therefore we exit this loop also and return our final count which is 2.
Time Complexity

O(N * M), where ‘N' and ‘M’ are the lengths of String ‘S’ and ‘P’ respectively. 

 

As for every index we’re checking if there is a substring that is equal to ‘P’ or not, hence we’re using nested loops for that. The outer loop runs from 0 to “N - M” and the inner loop runs from 0 to ‘M’. 

Space Complexity

O(1)

Since we are using constant extra memory

Code Solution
(100% EXP penalty)
Z Algorithm
Full screen
Console