Author: Shivam Garg
Tester: Shiv Dhingra
DIFFICULTY
MEDIUM HARD
PREREQUISITES
DP , Merge Sort Tree
PROBLEM
Given two arrays of strings, it is required to print the number of ways such that an equal-sized subarray can be extracted from both the arrays and satisfies certain LCS (Longest Common Substring) conditions.
EXPLANATION
If the conditions in the mentioned question are observed carefully, one will notice that we can
create a matrix X of size N*M, with X(i)(j) = (LCS(i,j)>=K).
The LCS of all the pairs can be found out easily via DP or Suffix Array.
Now, the matrix X is a binary-matrix.
From the conditions, it is quite evident that we need to find a square with the following structure -
This square will have 1s on all of its borders as well as on the 45-degree diagonal. Other elements can be 0/1.
In other words, we need to find the number of such squares possible in the given matrix.
Now, how to find this?
Well, the diagonals play an important role here. There are a total of N+M diagonals.
So, what we need to find out is-"How many square sub-matrices have their principal diagonal on this particular diagonal?"
The matrix in the above image is matrix X. We iterate over the diagonals and find how many such required squares lie on that diagonal.
For each (i,j), we compute DP1[i][j] where DP1[i][j] = min of continuous 1’s towards right, up and upward direction in diagonal.
DP1[i][j] is min ( continuous\hspace{1 mm} 1's\hspace{1 mm} towards \hspace{1 mm}right, towards \hspace{1 mm}up, towards\hspace{1 mm} upward \hspace{1 mm}direction \hspace{1 mm}in \hspace{1 mm}diagonal)
Also, we compute DP2[i][j] where DP2[i][j] = min of continuous 1’s towards left, down and downward direction in diagonal.
This can be accomplished using DP.
Now, for each diagonal, we compute RIGHT [ ] array and LEFT [ ] array. They can be obtained from above DP1 [ ] [ ] and DP2 [ ] [ ] VALUES.
RIGHT(i) will be the scope of the square with the bottom-left corner on this diagonal towards the right.
LEFT(i) will be the scope of the square with the top-right corner on this diagonal towards the left.
Now, all we need is that within the range of RIGHT(i), how many LEFT(i) occur such that LEFT(i) covers i.
In other words, let RIGHT(i) be A. Then, in the range j\in[i,i+A-1], how many LEFT(j) occur such that j-LEFT(j)+1 is less than or equal to i.
This can be solved via Merge Sort Tree
SOLUTION
Setter’s Solution -
[10]
Tester's Solution -