Z Algorithm Problem Statement

You are provided with a string S of length N and a string P of length M. Your objective is to determine the number of times P appears in S in linear time.

Example:

Input:
S = "ababa", P = "ab"
Output:
2
Explanation:

The string "ab" occurs twice in the string "ababa".

Constraints:

  • The string consists only of lowercase English alphabets.
  • 1 <= T <= 100
  • 1 <= N, M <= 10^4
  • Time Limit: 1 sec

Input:

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, representing the lengths of strings 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:

The output for each test case is a single integer indicating the number of occurrences of P in S.

Note:

You do not need to print anything; it has already been handled. Simply implement the function to return the result.
AnswerBot
2d

Implement a function to count the number of occurrences of a given string within another string in linear time.

  • Use the Z algorithm to preprocess the pattern string and the concatenated string to effic...read more

Help your peers!
Add answer anonymously...
Barclays Business Technology Analyst Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter