## Hashbrown

View as PDF

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 numbers. His favorite hashbrown is defined as a series of numbers. On the conveyor belt, you must count all contiguous subarrays that exactly matches the hashbrown.

#### Input Specification

The first line contains: and , representing the length of the conveyor belt, and the length of the hashbrown respectively.

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

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

Each number in the conveyor belt, and hashbrown respects the limits of .

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