Hashbrown

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types

Adam loves hashbrowns, specifically, hashbrowns that his factory produces. So, he asked you to pay a visit to his factory and count the number of favorite hashbrowns on a conveyor belt of N numbers. His favorite hashbrown is defined as a series of M numbers. On the conveyor belt, you must count all contiguous subarrays that exactly matches the hashbrown.

Input Specification

The first line contains: N and M (1 \le M \le N \le 500\,000), representing the length of the conveyor belt, and the length of the hashbrown respectively.

On the next line, there are N space separated numbers, which is the conveyor belt.

On the third line, there are M space separated numbers, which is the hashbrown.

Each number a_i in the conveyor belt, and hashbrown respects the limits of (1 \le a_i \le 1000).

Output Specification

On a single line, output the number of occurrences of the hashbrown on the conveyor belt.

Sample Input

13 6
4 1 1 2 5 5 7 1 2 5 5 7 1
1 2 5 5 7 1

Sample Output

2

Explanation

In this example, the sequence 1 2 5 5 7 1 occurs twice in the conveyor belt.

The first occurrence of this sequence is at index 2 (starting from 0).

4 1 [1 2 5 5 7 1] 2 5 5 7 1

As shown by the brackets.

The second occurrence of the sequence is at index 7.

4 1 1 2 5 5 7 [1 2 5 5 7 1]


Comments

There are no comments at the moment.