问题 G: sequence

问题 G: sequence

时间限制: 1 Sec  内存限制: 128 MB
提交: 751  解决: 156
[状态] [讨论版] [提交] [命题人:]
题目描述

给定一个含n个数的序列A和一个含m (m<=n) 个数的序列B

询问在A中有多少段连续的长为m的子序列Ak,Ak+1,…,Ak+m-1使得对于任意1<=i, j<=m满足Ak+i-1-Bi=Ak+j-1-Bj

输入

第一行两个整数nm (1 <= m <= n <= 106)

接下来一行n个整数,描述序列A (Ai <= 109)

接下来一行m个整数,描述序列B (Bi <= 109)

输出

输出一个数表示答案

样例输入 Copy
7 4
6 6 8 5 5 7 4
7 7 9 6
样例输出 Copy
2