Поиск подстроки в 2d массиве в C - PullRequest
Новая
       18

Поиск подстроки в 2d массиве в C

0 голосов
/ 14 апреля 2020

Это что-то для поиска подстроки в массиве 2d 

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;
}

Вывод: 

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

Таким образом, функция возвращает начальную точку SHOUT, которая равна 12, но когда я попытаться найти слово KEREM, оно должно дать мне 110, но вместо этого оно возвращает -1, что говорит о том, что слово не существует. Кажется, что код ищет только первые 3 строки, каждый ввод, который я ввожу, после этого возвращает -1. Не могли бы вы мне помочь? Я новичок. Это только первая часть, которая мне нужна, чтобы она искала в каждом направлении. Я могу написать 4 отдельные функции и вызвать их, если они не возвращают -1, но сначала мне нужно, чтобы это работало.

1 Ответ

1 голос
/ 14 апреля 2020

Хорошо, я сделал несколько ускорений и упрощений.

Нет необходимости в отдельном counting [по крайней мере слева направо и справа налево], как вы можете использовать wordidx

Кроме того, как только вы найдете совпадение на внутренней l oop, нет необходимости продолжать его. И вы можете остановить внешнюю l oop рано

Это быстрее вычислить длину str1 вне вызова и передать length в качестве аргумента. Кроме того, strlen должно работать очень хорошо.

Слева направо нет необходимости от j до go вплоть до COLUMN - 1, так как последние N слотов могут не соответствует, если на строке матрицы недостаточно места для выполнения оставшейся длины строки.

Кроме того, это неопределенное поведение, поскольку вы перетекаете в следующую строку. Это было бы безопасно (но неверно), за исключением последней строки, где вы будете go за концом всей матрицы.

Итак, я добавил jmax значение COLUMN - length

Справа налево немного сложнее. Трюк jmax очень важен.

Итак, вот две функции [они компилируются без ошибок, но я не проверил их]: 

#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;
}
...