Пошук найбільшого спільного підрядка

Найбільший спільний підрядок (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

Заповнивши таблицю для слів “диск” та “стиск” отримаємо:

Д И С К
С 0 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();
    }
}

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

Дивіться також: