-1

Given two rectangles, of size M * N and X * Y respectively. We need to find biggest square common among those that can be obtained by deleting some rows and columns of given rectangle. Its like finding common sequence in 2D. I know how to do it in 1 dimensional but how it can be modified for this problem.

Example :

Let first rectangle is of 3 * 4

1 2 0 5
1 2 1 6
1 2 3 7

Let second rectangle is 3 * 3

0 1 2
1 1 2
3 1 2

So here size of biggest common sub square is 2.

We can assume that 1 ≤ N, M, X, Y ≤ 700 and all numbers in both rectangles are integers in the interval [1, 1000].

I am looking for something O(N^3) solution. My current approach for this is try for every square in first grid, and try to fit it in second grid. It is very time consuming because for every subsquare you are using O(N^3) And then for looking weather its present in second one we need O(N^2).

mat7
  • 297
  • 3
  • 11
  • You can use something like [this answer](http://stackoverflow.com/a/22495382/916657) with a generalized suffix array I believe. You will get O(n^3). – Niklas B. Aug 15 '15 at 09:27
  • @NiklasB. Its a little twisted for this one I guess. Can you please explain bit more? – mat7 Aug 15 '15 at 09:36
  • Concatenate the rows of both matrices separated by a special character $, in your example yielding two strings `S_1_0 = 1205$1216$1237$` and `S_1_1 = 012$112$312$`. Build the suffix arrays of those strings and find their longest common substring using the standard algorithm. Continue to build the suffix arrays of consecutive 2-rows: `S_2_0 = (1,1)(2,2)(0,1)(5,6)$(1,1)(2,2)(1,3)(6,7)$, S_2_1 = (0,1)(1,1)(2,2)$(1,3)(1,1)(2,2)$`. Represent the tuples by their rank, which you can figure out by the suffix arrays of previous iterations. Again find the LCS. Continue like this. – Niklas B. Aug 15 '15 at 09:50
  • @NiklasB. Assuming I have code to build suffix array and find LCS can i please write out some pseudocode to make it more clear – mat7 Aug 15 '15 at 10:21
  • @mat7 Sorry, that's already a pretty detailed description. I don't have the time to write a full answer right now, but please refer to the answer I linked to, which has more information. Also check out the comments there – Niklas B. Aug 15 '15 at 10:22
  • @NiklasB. I did not get this part "Represent the tuples by their rank, which you can figure out by the suffix arrays of previous iterations. Again find the LCS. Continue like this." – mat7 Aug 15 '15 at 10:26
  • #NiklasB This looks like a different problem. It's a generalisation of the longest common *subsequence* problem, and you appear to be thinking about the longest common *substring* problem. One is contiguous and the other is not. – n. m. could be an AI Aug 15 '15 at 10:42
  • @n.m You're right actually, I missed that part of the question – Niklas B. Aug 15 '15 at 10:43
  • In that case, the problem is NP-hard, so probably there exists no polynomial time solution – Niklas B. Aug 15 '15 at 10:47
  • Please flag this question. Its from a running contest [August Clash](https://www.hackerearth.com/august-clash-15/algorithm/rasta-and-kheshtak/) on HackerEarth. – Ravi Ojha Aug 15 '15 at 11:20
  • This question is from a running contest on HackerEarth https://www.hackerearth.com/august-clash-15/ – Sachin Aug 15 '15 at 18:35

1 Answers1

2

The problem is NP-hard as per reduction from CLIQUE: Given a graph G = (V, E), define a matrix M_ij = 1, if (i,j) in E, M_ii = 2 for each i and M_ij = 0 otherwise. Then the graph has a k-Clique iif the largest common (square) submatrix of M and the matrix A of size k x k with only ones in it has size k.

Finding an O(n^3) algorithm to the problem would thus prove P = NP.

Niklas B.
  • 92,950
  • 18
  • 194
  • 224
  • @mat7 All known algorithms are exponential. – Niklas B. Aug 15 '15 at 10:56
  • What if we need to find substring only ? Can you explain a bit more for it – mat7 Aug 15 '15 at 10:57
  • @mat7 I've written a rather lengthy comment about it above. As for using ranks instead of tuples, it's just to compress the representation. You can't *actually* have n-tuples as characters, that would take too much space – Niklas B. Aug 15 '15 at 11:01