Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

fast algorithm for finding largest overlapping submatrix

hitorijanaihitorijanai Posts: 1Member
Question:
There was two matrixs with random size. The size range from the smallest 1x1 to the biggest 75x75.
Note, the row and column don't always have the same size, and the size of the second matrix also don't always have the same size as matrix 1.
In this lesson, you'll check if the two matrix is overlapping. Overlapping is if there are sub-matrixs (at least has 1 cell, 1x1) from the second matrix which is identical and at least has one sub-matrixs that cover the edge of its origin matrix.

The program you make must be able to get the size of the biggest overlapping sub-matrix and produce an output of the amount of row and column of the sub-matrix(with largest cell) which overlapped.
If nothing overlapped then the output is "0 0".

Example of Matrix one:
1 2 3
4 5 6
7 8 9
And Matrix two:
7 8 9
2 3 6
5 6 1

Overlapped at 1x1
1
And 1x3 sized sub-matrix
7 8 9

Also 2x2 sized sub-matrix
2 3
5 6

And the biggest is 2x2 (4 cells). Projection of this sub-matrix:
[code] 7 8 9
1 [b]2 3[/b] 6
4 [b]5 6[/b] 1
7 8 9[/code]

The input format is like this(for the above example):
3 3 {amount of row and column of the first matrix}
1 2 3
4 5 6 {matrix 1 data}
7 8 9
3 3 { amount of row and column of the second matrix}
7 8 9
2 3 6 {matrix 2 data}
5 6 1

The output format is two numbers in one line divided by one space.
So the output format for the above example is:
2 2

Comments

  • freelance starfreelance star Posts: 73Member
    : Question:
    : There was two matrixs with random size. The size range from the
    : smallest 1x1 to the biggest 75x75.
    : Note, the row and column don't always have the same size, and the
    : size of the second matrix also don't always have the same size as
    : matrix 1.
    : In this lesson, you'll check if the two matrix is overlapping.
    : Overlapping is if there are sub-matrixs (at least has 1 cell, 1x1)
    : from the second matrix which is identical and at least has one
    : sub-matrixs that cover the edge of its origin matrix.
    :
    : The program you make must be able to get the size of the biggest
    : overlapping sub-matrix and produce an output of the amount of row
    : and column of the sub-matrix(with largest cell) which overlapped.
    : If nothing overlapped then the output is "0 0".
    :
    : Example of Matrix one:
    : 1 2 3
    : 4 5 6
    : 7 8 9
    : And Matrix two:
    : 7 8 9
    : 2 3 6
    : 5 6 1
    :
    : Overlapped at 1x1
    : 1
    : And 1x3 sized sub-matrix
    : 7 8 9
    :
    : Also 2x2 sized sub-matrix
    : 2 3
    : 5 6
    :
    : And the biggest is 2x2 (4 cells). Projection of this sub-matrix:
    : [code]: 7 8 9
    : 1 [b]2 3[/b] 6
    : 4 [b]5 6[/b] 1
    : 7 8 9[/code]:
    :
    : The input format is like this(for the above example):
    : 3 3 {amount of row and column of the first matrix}
    : 1 2 3
    : 4 5 6 {matrix 1 data}
    : 7 8 9
    : 3 3 { amount of row and column of the second matrix}
    : 7 8 9
    : 2 3 6 {matrix 2 data}
    : 5 6 1
    :
    : The output format is two numbers in one line divided by one space.
    : So the output format for the above example is:
    : 2 2
    :
    The generalized version of it is maximum subset following a criteria
    [B][link=http://expert.myitcareer.org/]Freelance Programmer[/link]|[link=http://myitcareer.org/]Interview Question And Answer[/link][/B]
  • bau_asembau_asem Posts: 1Member
    anybody have the algorithm ?
    or c++ code will be better
    LOL
Sign In or Register to comment.