Рубрики

Алгоритм Манахера — длинная палиндромная подстрока линейного времени — часть 1

По заданной строке найдите самую длинную подстроку — палиндром.

  • если заданная строка «forgeeksskeegfor», вывод должен быть «geeksskeeg»
  • если заданная строка «abaaba», вывод должен быть «abaaba»
  • если заданная строка «abababa», вывод должен быть «abababa»
  • если заданная строка «abcbabcbabcba», вывод должен быть «abcbabcba»

Мы уже обсуждали наивный [O (n 3 )] и квадратичный [O (n 2 )] подходы в множестве 1 и множестве 2 .
В этой статье мы поговорим об алгоритме Манахера, который находит самую длинную палиндромную подстроку за линейное время.
Один из способов ( набор 2 ) найти палиндром — начать с центра строки и сравнить символы в обоих направлениях по одному. Если соответствующие символы с обеих сторон (слева и справа от центра) совпадают, то они образуют палиндром.
Давайте рассмотрим строку «abababa».
Здесь центр строки — 4-й символ (с индексом 3) b. Если мы сопоставляем символы слева и справа от центра, все символы совпадают, и поэтому строка «abababa» является палиндромом.

                    

Здесь центральная позиция — это не только фактическая позиция строки, но и позиция между двумя символами.
Рассмотрим строку «abaaba» четной длины. Эта строка является палиндромом вокруг позиции между 3-м и 4-м символами a и a соответственно.

                    

Чтобы найти самую длинную палиндромную подстроку из строки длиной N, используйте один из возможных 2 * N + 1 центров (N позиций символов, N-1 между двумя позициями символов и 2 позициями на левом и правом концах). совпадайте в левом и правом направлениях в каждом 2 * N + 1 центрах и отслеживайте LPS. Этот подход занимает O (N ^ 2) времени, и это то, что мы делаем в наборе 2 .

Давайте рассмотрим две строки «abababa» и «abaaba», как показано ниже:

                    
                    

В этих двух строках левая и правая части центральных положений (позиция 7 в первой строке и позиция 6 во второй строке) симметричны. Почему? Потому что вся строка — палиндром вокруг центральной позиции.
Если нам нужно вычислить самую длинную палиндромную подстроку в каждой позиции 2 * N + 1 слева направо, то симметричное свойство палиндрома может помочь избежать некоторых из ненужных вычислений (например, сравнение символов). Если есть палиндром некоторой длины L с центром в любой позиции P, то нам, возможно, не нужно сравнивать все символы в левой и правой части в позиции P + 1. Мы уже рассчитали LPS в позициях до P, и они могут помочь избежать некоторых сравнений после позиции P.
Такое использование информации с предыдущих позиций в более поздний момент времени делает алгоритм Манахера линейным. В наборе 2 нет повторного использования предыдущей информации, поэтому она является квадратичной.

Алгоритм Manacher, вероятно, считается сложным для понимания, поэтому здесь мы обсудим его настолько подробно, насколько сможем. Некоторые из его частей могут потребовать многократного чтения, чтобы понять это правильно.

Давайте посмотрим на строку «abababa». На третьем рисунке выше показаны 15 центральных позиций. Нам нужно рассчитать длину самой длинной палиндромной струны в каждой из этих позиций.

  • В позиции 0 вообще нет LPS (нет символа для сравнения слева), поэтому длина LPS будет равна 0.
  • В позиции 1 LPS равен a, поэтому длина LPS будет равна 1.
  • В позиции 2 LPS вообще отсутствует (левый и правый символы a и b не совпадают), поэтому длина LPS будет равна 0.
  • В позиции 3 LPS находится на расстоянии, поэтому длина LPS будет равна 3.
  • В позиции 4 вообще нет LPS (левый и правый символы b и a не совпадают), поэтому длина LPS будет равна 0.
  • В позиции 5 LPS — это ababa, поэтому длина LPS будет 5.

…… и так далее

Мы храним все эти палиндромные длины в массиве, скажем L. Тогда строки S и LPS Length L выглядят следующим образом:

                    

Аналогично, длина LPS L строки «abaaba» будет выглядеть так:

                    

В LPS Array L:

  • Значение длины LPS в нечетных позициях (фактические позиции символов) будет нечетным и будет больше или равно 1 (1 будет получено от самого центрального символа, если в левой и правой частях ничего не совпадает)
  • Значение длины LPS в четных позициях (позиции между двумя символами, крайними левыми и правыми позициями) будет четным и больше или равно 0 (0 появится, когда не будет совпадения в левой и правой частях)

Положение и индекс для строки здесь две разные вещи. Для заданной строки S длины N индексы будут от 0 до N-1 (всего N индексов), а позиции будут от 0 до 2 * N (всего 2 * N + 1 позиций).

Значение длины LPS можно интерпретировать двумя способами: один с точки зрения индекса и второй с точки зрения положения. Значение LPS d в положении I (L [i] = d) говорит о том, что:

  • Подстрока из позиции id в i + d является палиндромом длины d (в терминах позиции)
  • Подстрока из индекса (id) / 2 в [(i + d) / 2 — 1] является палиндромом длины d (в пересчете на индекс)

например, в строке «abaaba» L [3] = 3 означает, что подстрока от позиции 0 (3-3) до 6 (3 + 3) является палиндромом, который имеет «aba» длины 3, это также означает, что подстрока из индекса 0 [(3-3) / 2] — 2 [(3 + 3) / 2 — 1] — палиндром, который имеет «аба» длины 3.

                    

Теперь основной задачей является эффективное вычисление массива LPS. Как только этот массив вычислен, LPS строки S будет центрирован в позиции с максимальным значением длины LPS.
Мы увидим это во второй части .

Эта статья предоставлена Анураг Сингх . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Алгоритм Манахера — длинная палиндромная подстрока линейного времени — часть 1

0.00 (0%) 0 votes