# 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.