Similarity number for two arrays X and Y, each with size N, is defined as the number of pairs of indices (i,j) such that X[i]=Y[j] , for 1<=i,j
Now we are given two arrays, of size N and M. We need to find the number of sub arrays of equal sizes from these two arrays such that the similairty number of each subarray pair is greater or equal to given number K.
Example, say we have N=3, M=3, K=1 and arrays be [1,3,4] and [1,5,3] then here answer is 6
Explanation :
({1},{1})
({3},{3})
({1,3},{1,5})
({1,3},{5,3})
({3,4},{5,3})
({1,3,4},{1,5,3})
so ans = 6
How to solve it for given arrays of size N,M and given integer K. Number of elements can't be more than 2000. K is also less than N*M
Approach : Form all subarrays from array 1 of size N, those will be N*(N+1)/2 And same for array 2 of size M. Then try to find similarity number between each subarray pair. But this is very unoptimised way of doing it. What can be better way to solve this problem ? I think Dynamic programming can be used to solve this. Any suggestions ?
For {1,1,2} and {1,1,3} and K=1
{[1(1)],[1(1)]}
{[1(1)],[1(2)]}
{[1(2)],[1(1)]}
{[1(2)],[1(2)]}
{[1(1),1(2)],[1(1)]}
{[1(1),1(2)],[1(2)]}
{[1(1)],[1(1),1(2)]}
{[1(2)],[1(1),1(2)]}
{[1(1),1(2)],[1(1),1(2)]}
{[1(2),2],[1(2),3]}
{[1(1),1(2),2],[1(1),1(2),3]}