RUNNING - Editorial (LOC APRIL 2016)

Practice

Contest

Author: Anurag Anand

Tester: Raju Varshney

Editorialist: Vaibhav Tulsyan & Raju Varshney

Easy-Medium

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.

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.

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.

Related problems

1 Like

u can apply z algorithm as well!!! this is a link to my code !! i have used z algorithm!!!
https://www.codechef.com/viewsolution/9978016

1 Like

I used KMPâ€¦

https://www.codechef.com/viewsolution/9976634

1 Like
//