How to seach a 2d array for another smaller 2d array

[Kevin]

Hey, I'm learning c++ and a program that I am suppose to make is
suppost to read in two .txt files (map.txt, and template.txt). I am
then suppost to put each character into a 2d array (one for each .txt
file). Then try and find if the combination in the template 2d array
is somewhere within the map 2d array. Then print out the what row and
column that it was found at.

I have gotten the two files into seperate 2d arrays:

char ** map = new char*[numLines];

for (int i = 0; i < numLines; i++)
map[i] = new char [length+1];

in.clear();
in.seekg(0);

for (int i = 0; (i < numLines) && (!in.eof()); i++)
{
in.getline(buffer, 100);
strcpy(map[i], buffer);
}

and

char ** temp = new char*[numLines2];

for (int i = 0; i < numLines2; i++)
temp[i] = new char [length2+1];

inTemp.clear();
inTemp.seekg(0);

for (int i = 0; (i < numLines2) && (!inTemp.eof()); i++)
{
inTemp.getline(buffer, 100);
strcpy(temp[i], buffer);
}

But now I am suppost to see if the temp array is inside the map array,
and I'm abit lost. I got the program to work for the default files:

map:
j2DikxdiLLI3j
aAxzZxxixxkw9
okxjzxxxnchnq
jmxmbkklmnsff

temp:
xx
xx

to output the correct information:"Located at row 1, column 5"

//Searching for the temp in the map file

bool found = 0;
int loccol = 0;
int locrow = 0;

for (int i = 0; (i < numLines - 1) && !found; i++) // i runs through
rows
{
for (int j = 0; (j < length - 1) && !found; j++) // j runs through
cols
{
if(map[i][j] == temp[0][0] && map[i+1][j] == temp[1][0] &&
map[i][j+1] == temp[0][1] && map[i+1][j+1] == temp[1][1])
{
found = 1;
loccol = j; // j (columns) are the x coordinate
locrow = i; // i (rows) are the y coordinate
}
}
}

if (found)
cout << "Located at row " << locrow << ", column " << loccol << endl;
else
cout << "Not found" << endl;
But now I need to get it to search if the arrays chage size, and I
can't figure out how to do it.

Any help would be appreciated.

Thanks

[Victor Bazarov]

Kevin wrote:

[..]
for (int i = 0; (i < numLines - 1) && !found; i++) // i runs through
rows
{
for (int j = 0; (j < length - 1) && !found; j++) // j runs through
cols
{
if(map[i][j] == temp[0][0] && map[i+1][j] == temp[1][0] &&
map[i][j+1] == temp[0][1] && map[i+1][j+1] == temp[1][1])
{
found = 1;
loccol = j; // j (columns) are the x coordinate
locrow = i; // i (rows) are the y coordinate
}
}
}

if (found)
cout << "Located at row " << locrow << ", column " << loccol << endl;
else
cout << "Not found" << endl;
But now I need to get it to search if the arrays chage size, and I
can't figure out how to do it.

The 'if' statement inside the loop needs to be converted into two more
nested loops -- going through the elements of the smaller "template".

for (int i = ...
for (int j = ...
// optimization - only start looping if the top left corner
// of the 'template' is not the same as the current
if (map[i][j] == temp[0][0]) {
for (int n = ... // all rows of the template
for (int m = ... // all columns of the template
if (not ... // not equal
goto next_main_element;
} // end-for(m)
} // end-for(n)
found = 1;
} // end-if
next_main_element:
} // end-for (j)
} // end-for (i)

Also, there is no need to iterate through all elements of the main matrix,
only through the top left part leaving the stripe as wide as the template
width/height minus 1 on the right and on the bottom, because the template
would not fit there for comparison.

V
--
Please remove capital As from my address when replying by mail