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

Наибольшая общая подстрока (longest common substring) – подстрока максимальной длины, входящая в две или больше строки.

Алгоритм поиска наибольшей общей подстроки

Для решения задачи поиска общей подстроки максимальной длины строк A и B, необходимо заполнить таблицу Array размером n на m, где n и m - длины первой и второй строк, по следующим правилам:

  • Если A[i] == B[j] то:
    • для i == 0 or j == 0, Array[i, j] = 1
    • для i > 0 and j > 0, Array[i, j] = Array[i - 1, j - 1] + 1

Заполнив таблицу для слов “писк” и “поиск” получим:

П И С К
П 1 0 0 0
О 0 0 0 0
И 0 1 0 0
С 0 0 2 0
К 0 0 0 3

Получаем наибольшую подстроку: “ИСК”.

Реализация поиска

using System;


class Program
{
    static string LongestCommonSubstring(string a, string b)
    {
        var n = a.Length;
        var m = b.Length;
        var array = new int[n, m];
        var maxValue = 0;
        var maxI = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (a[i] == b[j])
                {
                    array[i, j] = (i == 0 || j == 0)
                        ? 1
                        : array[i - 1, j - 1] + 1;
                    if (array[i, j] > maxValue)
                    {
                        maxValue = array[i, j];
                        maxI = i;
                    }
                }
            }
        }

        return a.Substring(maxI + 1 - maxValue, maxValue);
    }

    static void Main(string[] args)
    {
        Console.Write("Первое слово: ");
        var s1 = Console.ReadLine();
        Console.Write("Второе слово: ");
        var s2 = Console.ReadLine();

        Console.WriteLine("Наибольшая общая подстрока: {0}", LongestCommonSubstring(s1, s2));
        Console.ReadLine();
    }
}

Результат работы программы:

Смотрите также: