Problem Link
Author: Anurag Anand
Tester: Raju Varshney
Editorialist: Vaibhav Tulsyan & Raju Varshney
Difficulty
Easy-Medium
Pre-requisites
KMP Algorithm
Problem
Given a sequence of distances of N poles from a point (D), and another record of distances (R) of length K, find the number of distinct starting points in D such that the consecutive distances from each starting point matches the sequence R exactly.
Quick Explanation
Create a consecutive-difference array for elements of D, and use KMP algorithm to find number of occurences of R.
Explanation
Let the sequence of distances of poles be represented by D_i and the sequence of recorded distances be R_j.
Since D_i represents the cumulative distance of i^{th} pole from the hostel, we need to maintain a difference array as we need to compare distances.
Let A_i represent an array of consecutive differences in D_i, that is, A_i = D_{i + 1} - D_i for i < N - 1.
Subtask 1:
Consider all sequences of length K and compare A_i with R_i. There are N - K + 1 possible starting points, and hence N - K + 1 such sequences.
For each sequence, we need to check whether the sequence matches with R or not.
Overall complexity: O(N*K)
However, this is not fast enough to solve Subtask 2 in the given time limit.
Subtask 2:
It can be noticed that the problem is identical to finding the number of occurences of sequence R in sequence A.
KMP Algorithm can be used to compute the number of occurences in O(N + K) time complexity.
This method is sufficient to pass both subtasks within time limit.
Similarly, other popular string matching algorithms like Rabin-Karp algorithm or Z-Algorithm can also be used instead of KMP algorithm.