1 Replies - 319 Views - Last Post: 01 March 2018 - 04:56 PM Rate Topic: -----

#1 gundream   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 01-March 18

Search 2d array inside a bigger 2d array

Posted 01 March 2018 - 04:32 PM

I have a 'philosophical' question.
I want to find if a big 2d array contains a smaller 2d array, and I'm going crazy.

BIGArray (5,5)
1 2 3 4 5
6 7 8 9 0
1 2 3 4 5
6 7 8 9 0
1 2 3 4 5

SMALLArray (3,2)
7 8 9
2 3 4

How could I know if...
Is SMALLArray inside BIGArray?
WHERE is it?
Is it repeated many times?

My research
First, I thought in 'brute force' testing, trying every value, but after some time, I thougt
that I could try just positions where SMALLArray is 'possible' (in my example, where a 7 is located).

How could I improve my algorithm?
I don't want code, just an 'I would do this'.

Thanks in advance.

Is This A Good Question/Topic? 0
  • +

Replies To: Search 2d array inside a bigger 2d array

#2 Martyr2   User is offline

  • Programming Theoretician
  • member icon

Reputation: 5226
  • View blog
  • Posts: 14,005
  • Joined: 18-April 07

Re: Search 2d array inside a bigger 2d array

Posted 01 March 2018 - 04:56 PM

Well, I think you are on the right track with the location of the 7. Think of it like a word search puzzle. You have a block of letters and you need to find words that go across down or diagonal (but in this case just across to get started). One way to attack that type of puzzle is to find a unique letter in the word you are looking for and then find that letter in the puzzle. Here you find the 7 and then check for 8 and 9 next to it. If you find that, then is the ones below it 2, 3 and 4?

To find the 7 you are looking at a straight linear search and then a few constant time accesses of the elements near it. This will help you locate if it contains the smaller 2D array, but then once you confirm or deny a match, you can go back to the linear search to locate the next 7 that might appear. This will essentially give you the number of times that it appears in the larger 2D array.

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1