**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 -
```