|
I I U P C 2 0 1 3 |
|
|
Problem H: Zero-Knowledge Protocol |
|
|
|
|
|
In cryptography, a zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true, without conveying any additional information apart from the fact that the statement is indeed true. We can extend these ideas to verify whether anyone has properly find any pattern in a data stream without enclosing which position these pattern is found.
So, in this problem, you have to exactly match multiple pattern of length M in a number stream of length N and prove it in zero-knowledge protocol. A pattern P of length M will exactly match with a sub-pattern of stream S in ith index, if and only if ,
P[1…M] = S[i….i+M-1] , i+M-1 ≤ N
In such case you have to sum i2 in zero-knowledge protocol and verify it. You can assume that all the pattern indexing is 1-based.
But, due to laziness and painfulness of generating multiple patterns, you have to use all the distinct permutations of given pattern P as multiple patterns.
|
|
|
Input |
|
|
First line of input will contain the number of test cases, T ≤ 50 to follow. Each test case starts with a line given N and M. Then follows two lines. First line contains N numbers si (1 ≤ i ≤ N) to denote number stream S and the next line contains M numbers pi (1 ≤ i ≤ M ) to denote pattern P.
Constraints
- 1 ≤ N, M ≤ 2*104 - 1 ≤ si , pi ≤ 109
|
|
|
Output |
|
|
For each case, print the total sum of squared match index in a single line. See the samples for exact formatting.
|
|
|
Sample Input |
Output for Sample Input |
|
2 3 2 10 11 10 10 11 4 3 10 11 11 10 10 11 11
|
5 5
|
|
|
|
|
Output Explanation
On the first test case two distinct permutation of P is possible. Pattern [10 11] is exactly matched with S in index 1 and pattern [11 10] is matched in index 2. So total sum in zero-knowledge protocol is 12 + 22 = 5.
On the second test case three distinct permutation of P is possible. Pattern [10 11 11] is exactly matched with S in index 1 and pattern [11 11 10] is matched in index 2. Pattern [11 10 11] doesn’t match anywhere. So total sum in zero-knowledge protocol is 12 + 22 = 5.
|
|
|
Problem Setter : Prasanjit Barua Alternate Solution : Mohammad Hafiz Uddin |
|