PROBLEM LINK:
Author: Aniket Marlapalle
Tester: Devamanyu Hazarika
Editorialist: Devamanyu Hazarika
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
z-algorithm (Any pattern searching algorithm)
PROBLEM:
The problem provides 3 integer arrays A, B, C. You have print the count of occurences such that C is a subarray of A starting from index i and B is a subarray of A starting from index j and i <= j .
EXPLANATION:
This question can be solved using the concept of pattern matching.
If we consider array A as the text and B and C as the pattern, we can identify their occurences in A in linear time using algorithms like Z-Algorithm or KMP-Algorithm.
Once the indices have been identified, all that remains is the sum of count of indices of B occurred in A that are >= j. Here j represents indices of C occurred in A.
So for every position j you can pre-calculate the number of occurences of C after that position.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.