Рубрики

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

В алгоритме Manacher — часть 1 мы рассмотрели некоторые основы и массив длины LPS.
Здесь мы увидим, как эффективно рассчитать массив длины LPS.

Чтобы эффективно рассчитать массив LPS, нам нужно понять, как длина LPS для любой позиции может относиться к значению длины LPS любой предыдущей уже рассчитанной позиции.
Для строки «abaaba» мы видим следующее:

                    

Если мы посмотрим вокруг позиции 3:

  • Значение длины LPS в позиции 2 и 4 одинаково
  • Значение длины LPS в позиции 1 и 5 одинаково

Мы вычисляем значения длины LPS слева направо, начиная с позиции 0, поэтому мы можем видеть, что мы уже знаем значения длины LPS в позициях 1, 2 и 3, тогда нам может не потребоваться вычислять длину LPS в позициях 4 и 5, потому что они равны значениям длины LPS в соответствующих позициях на левой стороне позиции 3.

Если мы посмотрим вокруг позиции 6:

  • Значение длины LPS в позиции 5 и 7 одинаково
  • Значение длины LPS в позиции 4 и 8 одинаково

…………. и так далее.
Если мы уже знаем значения длины LPS в позициях 1, 2, 3, 4, 5 и 6, то нам, возможно, не потребуется вычислять длину LPS в позициях 7, 8, 9, 10 и 11, поскольку они равны значениям длины LPS в соответствующие позиции на левой стороне позиции 6.
Для строки «abababa» мы видим следующее:

                    

Если мы уже знаем значения длины LPS в позициях 1, 2, 3, 4, 5, 6 и 7, то нам, возможно, не потребуется вычислять длину LPS в позициях 8, 9, 10, 11, 12 и 13, поскольку они равны Значения длины LPS в соответствующих позициях слева от позиции 7.

Вы видите, почему значения длины LPS симметричны вокруг позиций 3, 6, 9 в строке «abaaba»? Это потому, что вокруг этих позиций есть палиндромная подстрока. То же самое имеет место в строке «abababa» вокруг позиции 7.
Всегда ли верно, что значения длины LPS вокруг в центре палиндромного всегда симметричны (одинаковы)?
Ответ НЕТ.
Посмотрите на позиции 3 и 11 в строке «abababa». Обе позиции имеют длину LPS 3. Ближайшие левая и правая позиции симметричны (со значением 0), но не следующая. Положения 1 и 5 (вокруг положения 3) не симметричны. Аналогично, позиции 9 и 13 (вокруг позиции 11) не являются симметричными.

В этот момент мы можем видеть, что если в строке есть центр палиндрома с центром в некоторой позиции, то значения длины LPS вокруг центральной позиции могут быть или не быть симметричными в зависимости от некоторой ситуации. Если мы можем определить ситуацию, когда левая и правая позиции БУДУТ СИММЕТРИЧЕСКИ вокруг центральной позиции, нам НЕ НУЖНО вычислять длину LPS правой позиции, поскольку она будет точно такой же, как значение LPS соответствующей позиции на левой стороне, которая уже известна. И тот факт, что мы избегаем вычисления длины LPS в нескольких позициях, делает алгоритм Манахера линейным.

В ситуациях, когда левая и правая позиции НЕ БУДУТ СИММЕТРИЧЕСКИ вокруг центральной позиции, мы сравниваем символы в левой и правой сторонах, чтобы найти палиндром, но здесь также алгоритм пытается избежать определенных сравнений. Мы скоро увидим все эти сценарии.

Давайте введем несколько терминов, чтобы продолжить:

  • centerPosition — это позиция, для которой вычисляется длина LPS, и, скажем, длина LPS в centerPosition равна d (то есть L [centerPosition] = d)
  • centerRightPosition — это позиция, которая находится справа от centerPosition и расположена на расстоянии d от centerPosition (то есть centerRightPosition = centerPosition + d )
  • centerLeftPosition — это позиция, которая оставлена для centerPosition и расположена на расстоянии d от centerPosition (то есть centerLeftPosition = centerPosition — d )
  • currentRightPosition — это позиция, которая находится справа от centerPosition, для которого длина LPS еще не известна и должна быть рассчитана
  • currentLeftPosition — это позиция в левой части centerPosition, которая соответствует currentRightPosition
    centerPosition — currentLeftPosition = currentRightPosition — centerPosition
    currentLeftPosition = 2 * centerPosition — currentRightPosition
  • i-left palindrome — Палиндром i располагается слева от centerPosition, то есть в currentLeftPosition
  • i-right palindrome — палиндром i располагается справа от centerPosition, то есть в currentRightPosition
  • центр палиндрома — палиндром в центре

Когда мы находимся в centerPosition, для которого известна длина LPS, то мы также знаем длину LPS всех позиций, меньших, чем centerPosition. Допустим, длина LPS в centerPosition равна d, т.е.
L [centerPosition] = d

Это означает, что подстрока между позициями «centerPosition-d» — «centerPosition + d» является палиндромом.
Теперь мы продолжим вычислять длину позиции LPS больше, чем centerPosition.
Допустим, мы находимся в currentRightPosition (> centerPosition), где нам нужно найти длину LPS.
Для этого мы посмотрим на длину LPS currentLeftPosition, которая уже рассчитана.

Если LPS-длина currentLeftPosition меньше, чем «centerRightPosition — currentRightPosition», то LPS-длина currentRightPosition будет равна LPS-длине currentLeftPosition. Так
L [currentRightPosition] = L [currentLeftPosition], если L [currentLeftPosition] <centerRightPosition — currentRightPosition. Это первый случай .

Рассмотрим приведенный ниже сценарий для строки «abababa»:

                          (click to see it clearly)
                    

Мы вычислили длину LPS до позиции 7, где L [7] = 7, если мы рассматриваем позицию 7 как centerPosition, то centerLeftPosition будет 0, а centerRightPosition будет 14.
Теперь нам нужно рассчитать длину LPS других позиций справа от centerPosition.

Для currentRightPosition = 8, currentLeftPosition равно 6 и L [currentLeftPosition] = 0
Также centerRightPosition — currentRightPosition = 14 — 8 = 6
Случай 1 применяется здесь и поэтому L [currentRightPosition] = L [8] = 0
Случай 1 относится к позициям 10 и 12, поэтому
L [10] = L [4] = 0
L [12] = L [2] = 0

Если мы посмотрим на позицию 9, то:
currentRightPosition = 9
currentLeftPosition = 2 * centerPosition — currentRightPosition = 2 * 7 — 9 = 5
centerRightPosition — currentRightPosition = 14 — 9 = 5

Здесь L [currentLeftPosition] = centerRightPosition — currentRightPosition, поэтому вариант 1 здесь не применяется. Также обратите внимание, что centerRightPosition является крайним конечным положением строки. Это означает, что центральный палиндром является суффиксом входной строки. В этом случае L [currentRightPosition] = L [currentLeftPosition]. Это Дело 2 .

Случай 2 относится к позициям 9, 11, 13 и 14, поэтому:
L [9] = L [5] = 5
L [11] = L [3] = 3
L [13] = L [1] = 1
L [14] = L [0] = 0

Что на самом деле происходит в случае 1 и 2? Это просто использование палиндромного симметричного свойства и без какого-либо сопоставления символов, это поиск длины LPS новых позиций.

Если палиндром большей длины содержит палиндром меньшей длины, центрированный с левой стороны от его собственного центра, тогда на основе симметричного свойства будет другой такой же меньший палиндром, центрированный справа от большего центра палиндрома. Если меньший палиндром с левой стороны не является префиксом большего палиндрома, то применяется случай 1, а если это префикс, а больший палиндром является суффиксом самой входной строки, то применяется случай 2 .

Самый длинный палиндром, который я размещаю справа от текущего центра (i-правый палиндром), до тех пор, пока самый длинный палиндром, который я размещаю слева от текущего центра (i-левый палиндром), если i-левый палиндром полностью содержится в самом длинном палиндроме вокруг текущего центра (центральный палиндром), а i-левый палиндром не является префиксом центрального палиндрома ( случай 1 ) или (т. е. когда i-левый палиндром является префиксом центрального палиндрома), если центр Палиндром — это суффикс всей строки ( Случай 2 ).

В случае 1 и случае 2 i-правый палиндром не может расширяться больше, чем соответствующий i-левый палиндром (можете ли вы представить себе, почему он не может расширяться больше?), И поэтому длина LPS i-правого палиндрома точно такая же, как LPS длина и-левого палиндрома.

Здесь и палиндромы i-left и i-right полностью содержатся в центральном палиндроме (то есть L [currentLeftPosition] <= centerRightPosition — currentRightPosition)
Теперь, если i-left палиндром не является префиксом центрального палиндрома (L [currentLeftPosition] <centerRightPosition — currentRightPosition), это означает, что i-left палиндром не смог развернуться до позиции centerLeftPosition.

Если мы посмотрим на следующее с centerPosition = 11, то

                          (click to see it clearly)
                    

centerLeftPosition будет 11 — 9 = 2, а centerRightPosition будет 11 + 9 = 20
Если мы берем currentRightPosition = 15, его currentLeftPosition равно 7. Случай 1 применяется здесь, и поэтому L [15] = 3. i-левый палиндром в позиции 7 — это «bab», который полностью содержится в центральном палиндроме в позиции 11 (что означает « dbabcbabd»). Мы можем видеть, что i-правый палиндром (в положении 15) не может расширяться больше, чем i-левый палиндром (в положении 7).

Если бы была возможность расширения, i-левый палиндром мог бы уже расшириться. Но такой возможности нет, так как i-левый палиндром является префиксом центрального палиндрома. Таким образом, благодаря свойству симметрии, i-правый палиндром будет точно таким же, как и i-левый палиндром, и он не сможет больше расширяться. Это делает L [currentRightPosition] = L [currentLeftPosition] в случае 1.

Теперь, если мы рассмотрим centerPosition = 19, то centerLeftPosition = 12 и centerRightPosition = 26
Если мы берем currentRightPosition = 23, его currentLeftPosition будет равным 15. Случай 2 применяется здесь, и поэтому L [23] = 3. i-левый палиндром в позиции 15 — это «bab», который полностью содержится в центральном палиндроме в положении 19 (что означает « babdbab»). В случае 2, где i-левый палиндром является префиксом центрального палиндрома, i-правый палиндром не может расширяться больше, чем длина i-левого палиндрома, поскольку центральный палиндром является суффиксом входной строки, поэтому для сравнения и расширения больше не остается символа. , Это делает L [currentRightPosition] = L [currentLeftPosition] в случае 2.

Случай 1: L [currentRightPosition] = L [currentLeftPosition] применяется, когда:

  • я-левый палиндром полностью содержится в центре палиндрома
  • я-левый палиндром НЕ является префиксом центрального палиндрома

Оба вышеуказанных условия выполняются, когда
L [currentLeftPosition] <centerRightPosition — currentRightPosition

Случай 2: L [currentRightPosition] = L [currentLeftPosition] применяется, когда:

  • i-левый палиндром является префиксом центрального палиндрома (означает также полностью содержащийся)
  • центральный палиндром является суффиксом входной строки

Вышеуказанные условия выполняются, когда
L [currentLeftPosition] = centerRightPosition — currentRightPosition (для 1- го условия) AND
centerRightPosition = 2 * N, где N — длина входной строки N (для 2- го условия).

Случай 3: L [currentRightPosition]> = L [currentLeftPosition] применяется, когда:

  • i-левый палиндром является префиксом центрального палиндрома (и поэтому i-левый палиндром полностью содержится в центральном палиндроме)
  • центральный палиндром НЕ является суффиксом входной строки

Вышеуказанные условия выполняются, когда
L [currentLeftPosition] = centerRightPosition — currentRightPosition (для 1- го условия) AND
centerRightPosition <2 * N, где N — длина входной строки N (для 2- го условия).
В этом случае существует вероятность расширения i-правого палиндрома, поэтому длина i-правого палиндрома, по крайней мере, равна длине i-левого палиндрома.

Случай 4: L [currentRightPosition]> = centerRightPosition — currentRightPosition применяется, когда:

  • я-левый палиндром НЕ полностью содержится в центре палиндрома

Выше условие выполняется, когда
L [currentLeftPosition]> centerRightPosition — currentRightPosition
В этом случае длина i-правого палиндрома как минимум равна длине (centerRightPosition — currentRightPosition), и существует вероятность расширения i-правого палиндрома.

На следующем рисунке

                          (click to see it clearly)
                    

Если мы возьмем центральную позицию 7, тогда Случай 3 применяется в currentRightPosition 11, потому что i-левый палиндром в currentLeftPosition 3 является префиксом центрального палиндрома, а i-правый палиндром не является суффиксом входной строки, поэтому здесь L [11] = 9, что больше, чем длина i-левого палиндрома L [3] = 3. В этом случае гарантируется, что L [11] будет не менее 3, и поэтому при реализации мы сначала устанавливаем L [11] = 3, а затем мы пытаемся расширить его, сравнивая символы слева и справа, начиная с расстояния 4 (что касается расстояния 3, уже известно, что символы будут совпадать).

Если мы возьмем центральную позицию 11, тогда Случай 4 применяется в currentRightPosition 15, потому что L [currentLeftPosition] = L [7] = 7> centerRightPosition — currentRightPosition = 20 — 15 = 5. В этом случае гарантируется, что L [15] будет быть по крайней мере 5, и поэтому в реализации мы 1- й набор L [15] = 5, а затем мы пытаемся расширить его, сравнивая символы в левой и правой части, начиная с расстояния 5 (Как до расстояния 5, это уже Известно, что символы будут совпадать).

Теперь осталось обсудить один момент: когда мы работаем в одной центральной позиции и вычисляем длины LPS для разных правых позиций, как узнать, что будет следующей центральной позицией. Мы изменяем centerPosition на currentRightPosition, если палиндром с центром в currentRightPosition расширяется за пределами centerRightPosition.

Здесь мы видели четыре разных случая того, как длина LPS позиции будет зависеть от длины LPS предыдущей позиции.
В третьей части мы обсудили реализацию кода, а также по-разному рассмотрели эти четыре случая и реализовали их тоже.

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

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

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

0.00 (0%) 0 votes