5.2 🥔🫑 Good Vegetable Sets 🥕🍅
Alice is an urban gardener who loves growing a variety of vegetables in her small backyard. She has a garden bed where she plans to plant a set of vegetables represented by the array a of length n.
Alice also has a set of m specific vegetables she wants to grow, represented by the array b. She considers a subset of m vegetables from her garden bed to be a "good" set if they can be rearranged to match at least k of the vegetables in b.
For example, if b = [1, 2, 3, 4] and k = 3, then the vegetable sets [4, 1, 2, 3] and [2, 3, 4, 5] are good (they can be rearranged to match 3 or more vegetables in b), while [3, 4, 5, 6] and [3, 4, 3, 4] are not good.
Alice wants to count how many contiguous subsets of length m in her garden bed a will be considered good sets. In other words, she wants to find the number of positions 1 ≤ l ≤ n-m+1 such that the vegetables a[l], a[l+1], ..., a[l+m-1] form a good set.
Can you help Alice solve this problem?
Constraints
t(1≤t≤10^4)
n,m, and k(1≤k≤m≤n≤2*10^5)
a1,a2,…,an (1≤ai≤10^6)
b1,b2,…,bn (1≤ai≤10^6)
It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5 .Similarly, the sum of m over all test cases does not exceed 2*10^5.
Input Format
The first line contains an integer t — the number of test cases.
The first line of each test case contains three integers
n,m,k— the number of elements in arrays a and b, the required number of matching elements.
The second line of every test case contains n integers a1,a2,a3….an - the elements of array a
The third line of every test case contains m integers b1,b2,b3….bn - the elements of array b
Output Format
For each test case, output the number of good subsegments of array a on a separate line.
Example 1
Input:
5
7 4 2
4 1 2 3 4 5 6
1 2 3 4
7 4 3
4 1 2 3 4 5 6
1 2 3 4
7 4 4
4 1 2 3 4 5 6
1 2 3 4
11 5 3
9 9 2 2 10 9 7 6 3 6 3
6 9 7 8 10
4 1 1
4 1 5 6
6
Output:
4
3
2
4
1
Explanation:
Example is self explanatory
Log In to solve the Question