Ad

Searching For A Substring In 2d Array In C

- 1 answer

This is something for searching a substring In a 2d array

int left_to_rigth(char matrix[ROW][COLUNM], char str1[])
{
    int i = 0, j, counting = 0, wordcnt;
    int length = computeLength(str1);   //returns legth of string   
    int index = -1;

    for (i = 0; i < ROW; i++)
    {
        for (j = 0; j < COLUNM; j += 1)
        {
            if (matrix[i][j] == str1[0])
            {
                for (wordcnt = 0; wordcnt < length; wordcnt++)
                {
                    if (matrix[i][j + wordcnt] == str1[wordcnt])
                    {
                        counting++;
                    }
                }

                if (counting == length)
                {
                    index = (i *12) + j;
                }
            }
        }
    }

    return index;
}

The output:

Enter the string to be searched in the puzzle:
SHOUT
position in the puzzle: 12
PUZZLE(MATRIX)
X  T  Z  M  Q  Y  K  C  E  C  F  H -->0 1 2 3 4 5 6 7 8 9 10 11 
*S  H  O  U  T*  E  X  O  E  A  P  I -->12 13 14 ------------23
X  G  T  L  Q  B  E  L  T  N  F  K
A  I  R  I  D  Z  A  L  L  I  O  D
M  E  I  E  T  Y  S  E  H  R  T  I
A  W  B  R  N  E  T  C  W  O  H  X
N  O  U  I  R  U  Z  T  S  C  C  T
U  D  T  P  E  C  J  I  E  H  R  U
A  L  E  M  C  S  Y  O  N  I  U  R
L  V  *K  E  R  E  M*  N  I  P  H  E
E  A  N  B  U  R  E  J  O  N  C  Y
A  W  I  I  I  J  N  J  R  U  Y  F
D  W  T  N  T  H  E  N  P  J  Y  T
E  Q  L  Z  D  I  L  E  M  M  A  B
R  C  I  T  E  N  G  A  M  T  P  C

So the function returns the starting point of SHOUT which is 12 but when I try to search for the word KEREM it should give me 110 but instead it return -1 which says that the word doesnt exist. It seems like the code only searches for the first 3 lines every input I enter after that returns -1. Could you please help I am a beginner This is just the first part I need to make it so that it searches in every direction I can either write 4 seperate functions and call them if they dont return -1 but I need to get this working first

Ad

Answer

Okay, I've done a few speedups and simplifications.

No need for a separate counting [for left-to-right and right-to-left, at least] as you can use wordidx

Also, once you find a match on the inner loop, there is no need to continue with it. And, you can stop the outer loop early

It's faster to calculate the length of str1outside of the call and pass length as an argument. Also, strlen should work just fine.

On left-to-right, there is no need for j to go all the way to COLUMN - 1 as the last N slots can not match if there isn't enough room on the matrix line to fulfill the remaining string length.

Also, it's undefined behavior because you'll spill over into the next row. This would be harmless [but wrong result] except for the last row, where you'll go beyond the end of the entire matrix.

So, I added a jmax value of COLUMN - length

The right-to-left is slightly trickier. The jmax trick is critical.

So, here are the two functions [they compile cleanly, but I've not tested them]:

#include <string.h>

#define ROW     10
#define COLUMN  10

int
left_to_right(char matrix[ROW][COLUMN], const char *str1, int length)
{
    char *matcur;
    int i;
    int j;
    int wordidx;

    int jmax = COLUMN - length;

    int index = -1;

    jmax += 1;
    for (i = 0;  i < ROW;  ++i) {
        for (j = 0;  j < jmax;  ++j, ++matcur) {
            matcur = &matrix[i][0];

            if (matcur[0] != str1[0])
                continue;

            for (wordidx = 1;  wordidx < length;  ++wordidx) {
                if (matcur[wordidx] != str1[wordidx])
                    break;
            }

            if (wordidx == length) {
                index = (i * COLUMN) + j;
                break;
            }
        }

        if (index >= 0)
            break;
    }

    return index;
}

int
right_to_left(char matrix[ROW][COLUMN], const char *str1, int length)
{
    const char *matcur;
    int i;
    int j;
    int wordidx;

    int jmax = COLUMN - length;

    int index = -1;

    for (i = 0;  i < ROW;  ++i) {
        matcur = &matrix[i][jmax];

        for (j = jmax;  j >= 0;  --j, --matcur) {
            if (matcur[0] != str1[0])
                continue;

            for (wordidx = 0;  wordidx < length;  ++wordidx) {
                if (matcur[wordidx] != str1[wordidx])
                    break;
            }

            if (wordidx == length) {
                index = (i * COLUMN) + j;
                break;
            }
        }

        if (index >= 0)
            break;
    }

    return index;
}
Ad
source: stackoverflow.com
Ad