FINDEX - Editorial (NPLTZ15)

PROBLEM LINK:

Contest

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.

RELATED PROBLEMS:

2 Likes

Hi,
Can someone tell me what’s wrong with this solution?
I’ve been struggling with it for hours.
https://www.codechef.com/viewsolution/8650201