2

Я решаю задачу поиска наибольшей общей подстроки. Я использую функцию, опубликованную здесь: http://www.geeksforgeeks.org/longest-common-substring/

Вот она:

int LCSubStr(char *X, char *Y, int m, int n)
{
    int LCSuff[m+1][n+1];
    int result = 0;

    for (int i=0; i<=m; i++)
    {
        for (int j=0; j<=n; j++)
        {
            if (i == 0 || j == 0)
                LCSuff[i][j] = 0;

            else if (X[i-1] == Y[j-1])
            {
                LCSuff[i][j] = LCSuff[i-1][j-1] + 1;
                result = max(result, LCSuff[i][j]);
            }
            else LCSuff[i][j] = 0;
        }
    }
    return result;
}

Об этой задаче есть статья в Википедии. Некоторые вещи описаны в статьях:

В общем, в результате работы получается двумерный массив, максимальный элемент которого и обозначает длину наибольшей общей подстроки

Пример:

    SUBSEQUENCE
   000000000000
 S 010010000000
 U 002000010000
 B 000300000000
 E 000001001001
 U 001000010000
 E 000001002001
 N 000000000300
 C 000000000040
 S 010010000000

Длина наибольшей общей подстроки: 4

Как я могу получить саму подстроку? (например, в виде позиции вхождения в первую или вторую строки). Мне нужен не код, а алгоритм хотя бы. Как это математически высчитывается. У меня были догадки, но это всего лишь догадки.

1
  • 2
    Алгоритм вроде как очевидный: - находится максимальное число в массиве; - координаты числа - позиция последнего(!) символа наибольшей совпавшей последовательности; - для получения начала вхождения просто отнять от координат это самое число; - ну и для получения самой совпавшей строки можно вырезать из любой исходной строки символы слева, от полученной координаты с длиной этого максимального числа.
    – roach1967
    20 апр 2014 в 18:11

1 ответ 1

1

Лучше использовать плохой понятный алгоритм, чем хороший, но в котором Вы не разобрались. Вот неэффективно, зато интуитивно - http://www.cyberforum.ru/c-beginners/thread1127343.html

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.