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

Последовательность — это некий упорядоченный набор элементов. Строка — это частный случай последовательности. В свою очередь, под термином «наибольшая общая подстрока» мы будем понимать такую подстроку максимальной длины, которая входит в две или больше строки. Представленный ниже алгоритм также подойдет и для поиска наибольшей повторяющейся последовательности не только букв, но и, в принципе, любых символов, например, цифр.

Суть алгоритма

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

• Если A[i] == B[j] то:
  • для i == 0 || j == 0, Array[i, j] = 1
  • для i > 0 &&  j > 0,  Array[i, j] = Array[i — 1, j — 1] + 1

Например, рассмотрим две строки: «ПОИСК» и «ПИСК» (наибольшая повторяющаяся подстрока в этом случае — «ИСК»):

Реализация алгоритма поиска наибольшей повторяющейся подстроки в C#

Код консольного приложения для поиска набольшей повторяющейся подстроки представлен ниже:

using System;

namespace ConsoleApp1
{
    internal class Program
    {

        static string LCS(string a, string b)
        {
            var n = a.Length; //длина первой строки
            var m = b.Length; //длина второй строки
            var array = new int[n, m]; //создаем двумерный массив m x n
            var maxValue = 0;
            var maxI = 0;
            for (int i = 0; i < n; i++) //цикл по символам строки A
            {
                for (int j = 0; j < m; j++) //цикл по символам строки B
                {
                    if (a[i] == b[j]) //проверяем совпадают ли символы в позициях i и 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; //запоминаем позицию в строке A с которой необходимо начать копирование подстроки
                        }
                    }
                }
            }
            //возвращаем наибольшую повторяющуюся подстроку
            return a.Substring(maxI + 1 - maxValue, maxValue);
        }




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

            Console.WriteLine($"Наибольшая общая подстрока: {LCS(a, b)}");
            Console.ReadLine();
        }
    }
}

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

Итого

Для реализации алгоритма поиска наибольшей повторяющейся последовательности нам понадобились знания о том, что из себя представляет массив и умение работать с циклами (в данном случае — с циклом for).