Я согласен, что логика объяснения ссылки не совсем верна. Некоторые подробности я привожу ниже.

Алгоритм Манахера заполняет таблицу P [i], которая показывает, насколько далеко простирается палиндром с центром в i. Если P [5] = 3, то три символа по обе стороны от позиции пять являются частью палиндрома. Алгоритм использует тот факт, что если вы нашли длинный палиндром, вы можете быстро заполнить значения P на правой стороне палиндрома, посмотрев на значения P с левой стороны, так как они в основном должны быть такой же.

Я начну с объяснения случая, о котором вы говорили, а затем при необходимости расширю этот ответ.

R указывает индекс правой стороны палиндрома с центром в C. Вот состояние в указанном вами месте:

C=11
R=20
i=15
i'=7
P[i']=7
R-i=5

и логика такая:

if P[i']<=R-i:  // not true
else: // P[i] is at least 5, but may be greater

Псевдокод в ссылке указывает, что P [i] должно быть больше или равно P [i '], если тест не прошел, но я считаю, что он должен быть больше или равен R-i, и объяснение подтверждает это.

Поскольку P [i '] больше Ri, палиндром с центром в i' выходит за пределы палиндрома с центром в C. Мы знаем, что палиндром с центром в i будет иметь ширину не менее Ri символов, потому что до этой точки у нас все еще есть симметрия, но мы должны искать дальше этого.

Если бы P [i '] не было больше Ri, то самый большой палиндром с центром в i' находится внутри самого большого палиндрома с центром в C, поэтому мы бы знали, что P [i] не может быть больше P [i ']. Если бы это было так, мы получили бы противоречие. Это означало бы, что мы могли бы расширить палиндром с центром в i за пределы P [i '], но если бы мы могли, то мы также смогли бы расширить палиндром с центром в i' из-за симметрии, но это уже было должен быть как можно большим.

Этот случай проиллюстрирован ранее:

C=11
R=20
i=13
i'=9
P[i']=1
R-i=7

В этом случае P [i '] ‹= R-i. Поскольку мы все еще находимся на расстоянии 7 символов от края палиндрома с центром в C, мы знаем, что по крайней мере 7 символов вокруг i совпадают с 7 символами вокруг i '. Поскольку вокруг i 'был только один символьный палиндром, вокруг i также есть односимвольный палиндром.

j_random_hacker заметил, что логика должна быть примерно такой:

if P[i']<R-i then
  P[i]=P[i']
else if P[i']>R-i then
  P[i]=R-i
else P[i]=R-i + expansion

Если P [i '] ‹R-i, то мы знаем, что P [i] == P [i'], поскольку мы все еще внутри палиндрома с центром в C.

Если P [i ']> R-i, то мы знаем, что P [i] == R-i, потому что в противном случае палиндром с центром в C простирался бы за R.

Таким образом, расширение действительно необходимо только в особом случае, когда P [i '] == R-i, поэтому мы не знаем, может ли палиндром в P [i] быть длиннее.

Это обрабатывается в реальном коде, устанавливая P [i] = min (P [i '], R-i), а затем всегда расширяя. Такой способ выполнения не увеличивает временную сложность, потому что, если расширение не требуется, время, необходимое для выполнения расширения, постоянно.

Я нашел одно из лучших объяснений по следующей ссылке:

http://tarokuriyama.com/projects/palindrome2.php

Он также имеет визуализацию для того же примера строки (babcbabcbaccba), используемого в первой ссылке, упомянутой в вопросе.

Помимо этой ссылки, я также нашел код в

http://algs4.cs.princeton.edu/53substring/Manacher.java.html

Я надеюсь, что это будет полезно другим, пытающимся понять суть этого алгоритма.

Алгоритм на этом сайте кажется до некоторой степени понятным http://www.akalin.cx/longest-palindrome-linear-time

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

Сначала ответьте сами - когда вы найдете палиндром заданной длины, скажем, 5 - не можете ли вы в качестве следующего шага просто перейти к концу этого палиндрома (пропуская 4 буквы и 4 средних буквы)?

Если вы попытаетесь создать палиндром длиной 8 и разместить другой палиндром длиной> 8, центр которого находится справа от первого палиндрома, вы заметите что-то забавное. Попробуйте: палиндром длиной 8 - WOWILIKEEKIL - Like + ekiL = 8 Теперь в большинстве случаев вы можете записать место между двумя E как центр и число 8 как длину и перейти после последнего L, чтобы искать центр большего палиндрома.

Этот подход неверен, поскольку центр большего палиндрома может находиться внутри ekiL, и вы пропустите его, если прыгнете после последнего L.

После того, как вы найдете LIKE + EKIL, вы поместите 8 в массив, который используют эти алгоритмы, и это будет выглядеть так:

[0,1,0,3,0,1,0,1,0,3,0,1,0,1,0,1,8]

за

[#,W,#,O,#,W,#,I,#,L,#,I,#,K,#,E,#]

Хитрость в том, что вы уже знаете, что, скорее всего, следующие 7 (8-1) чисел после 8 будут такими же, как и слева, поэтому следующим шагом будет автоматическое копирование 7 чисел слева от 8 направо от 8, сохраняя помните, они еще не окончательные. Массив будет выглядеть так

[0,1,0,3,0,1,0,1,0,3,0,1,0,1,0,1,8,1,0,1,0,1,0,3] ( мы на 8)

за

[#,W,#,O,#,W,#,I,#,L,#,I,#,K,#,E,#,E,#,K,#,I,#,L]

Приведем пример, что такой скачок разрушит наше текущее решение, и посмотрим, что мы можем заметить.

WOWILIKEEKIL - давайте попробуем сделать палиндром побольше с центром где-нибудь внутри EKIL. Но это невозможно - нам нужно заменить слово EKIL на то, что содержит палиндром. Какие? ОООООх - вот и вся уловка. Единственная возможность иметь более крупный палиндром с центром в правой части нашего текущего палиндрома - это то, что он уже находится в правой (и левой) части палиндрома.

Давайте попробуем построить один на основе WOWILIKEEKIL. Нам нужно будет изменить EKIL, например, на EKIK, с I в качестве центра большого палиндрома - не забудьте также изменить LIKE на KIKE. Первыми буквами нашего хитрого палиндрома будут:

WOWIKIKEEKIK

как было сказано ранее - пусть последний я буду центром большего паллиндрома, чем КИКЕКИК:

WOWIKIKEEKIKEEKIKIW

давайте сделаем массив до нашего старого pallindrom и узнаем, как промыть дополнительную информацию.

за

[_ W _ O _ W _ I _ K _ I _ K _ E _ E _ K _ I _ K _ E _ E _ K _ I _ K _ I _ W ]

это будет [0,1,0,3,0,1,0,1,0,3,0,3,0,1,0,1,8

мы знаем, что следующий I - третий будет самым длинным паллиндромом, но давайте на время забудем об этом. позволяет скопировать числа в массиве слева от 8 вправо (8 чисел)

[0,1,0,3,0,1,0,1,0,3,0,3,0,1,0,1,8,1,0,1,0,3,0,3]

В нашем цикле мы находимся между буквами E с номером 8. Что особенного в I (будущая середина самого большого паллиндрома), что мы не можем перейти прямо к K (последней букве самого большого в настоящее время паллиндрома)? Особенность в том, что он превышает текущий размер массива ... как? Если вы переместите 3 пробела вправо от 3 - вы вне массива. Это означает, что это может быть середина самого большого паллиндрома, и дальше всего вы можете прыгнуть с этой буквы I.

Извините за длину этого ответа - я хотел объяснить алгоритм и могу вас заверить - @OmnipotentEntity был прав - я понял это даже лучше после объяснения вам :)

Полная статья: http://www.zrzahid.com/longest-palindromic-substring-in-linear-time-manachers-algorithm/

Прежде всего, давайте внимательно присмотримся к палиндрому, чтобы найти некоторые интересные свойства. Например, S1 = "abaaba" и S2 = "abcba", оба являются палиндромом, но какова нетривиальная (т.е. не длина или символы) разница между ними? S1 - это палиндром с центром в невидимом пространстве между i = 2 и i = 3 (несуществующее пространство!). С другой стороны, S2 сосредоточен вокруг символа i = 2 (т.е. c). Чтобы аккуратно обработать центр палиндрома независимо от нечетной / четной длины, давайте преобразуем палиндром, вставив специальный символ $ между символами. Тогда S1 = "abba" и S2 = "abcba" будет преобразовано в T1 = "$ a $ b $ a $ a $ b $ a $" с центром в i = 6 и T2 = "$ a $ b $ c $ b". $ a $ "с центром в i = 5. Теперь мы видим, что центры существуют, а длины согласованы 2 * n + 1, где n = длина исходной строки. Например,

                    i'          c           i           
      -----------------------------------------------------
      | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12|
      ----------------------------------------------------- 
   T1=| $ | a | $ | b | $ | a | $ | a | $ | b | $ | a | $ |
      -----------------------------------------------------

Затем заметьте, что из свойства симметрии (преобразованного) палиндрома T вокруг центра c, T [c-k] = T [c + k] для 0 ‹= k‹ = c. То есть позиции c-k и c + k зеркально отражают друг друга. Скажем иначе, для индекса i справа от центра c зеркальный индекс i 'находится слева от c, так что c-i' = i-c => i '= 2 * c-i и наоборот. Это,

For each position i on the right of center c of a palindromic substring, the mirror position of i is, i'=2*c-i, and vice versa.

Определим массив P [0..2 * n] такой, что P [i] равняется длине палиндрома с центром в i. Обратите внимание, что длина фактически измеряется количеством символов в исходной строке (игнорируя специальные символы $). Также пусть min и max будут соответственно крайней левой и крайней правой границами палиндромной подстроки с центром в c. Итак, min = c-P [c] и max = c + P [c]. Например, для палиндрома S = "abaaba" преобразованный палиндром T, центр зеркала c = 6, массив длин P [0..12], min = cP [c] = 6-6 = 0, max = c + P [c] = 6 + 6 = 12, и два образца зеркальных индексов i и i 'показаны на следующем рисунке.

      min           i'          c           i           max
      -----------------------------------------------------
      | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12|
      ----------------------------------------------------- 
    T=| $ | a | $ | b | $ | a | $ | a | $ | b | $ | a | $ |
      -----------------------------------------------------
    P=| 0 | 1 | 0 | 3 | 0 | 5 | 6 | 1 | 0 | 3 | 0 | 1 | 0 |
      -----------------------------------------------------

Имея такой массив длины P, мы можем найти длину самой длинной палиндромной подстроки, посмотрев на максимальный элемент P. То есть

P[i] is the length of a palindromic substring with center at i in the transformed string T, ie. center at i/2 in the original string S; Hence the longest palindromic substring would be the substring of length P[i_max] starting from index (i_max-P[i_max])/2 such that i_max is the index of maximum element in P.

Давайте нарисуем аналогичный рисунок ниже для нашего непалиндромного примера строки S = ​​"babaabca".

                       min              c               max
                       |----------------|-----------------|
      --------------------------------------------------------------------
 idx= | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|
      --------------------------------------------------------------------- 
    T=| $ | b | $ | a | $ | b | $ | a | $ | a | $ | b | $ | c | $ | a | $ |
      ---------------------------------------------------------------------
    P=| 0 | 1 | 0 | 3 | 0 | 3 | 0 | 1 | 4 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
      ---------------------------------------------------------------------

Вопрос в том, как эффективно вычислить P. Свойство симметрии предлагает следующие случаи, которые мы потенциально могли бы использовать для вычисления P [i], используя ранее вычисленное P [i '] в зеркальном индексе i' слева, таким образом пропуская много вычислений. Предположим, что у нас есть эталонный палиндром (первый палиндром) для начала.

1. A third palindrome whose center is within the right side of a first palindrome will have exactly the same length as that of a second palindrome anchored at the mirror center on the left side, if the second palindrome is within the bounds of the first palindrome by at least one character.

   For example in the following figure with the first palindrome centered at c=8 and bounded by min=4 and max=12, length of the third palindrome centered at i=9 (with mirror index i'= 2*c-i = 7) is, P[i] = P[i'] = 1. This is because the second palindrome centered at i' is within the bounds of first palindrome. Similarly, P[10] = P[6] = 0.

   
   
                                         |----3rd----|
                                 |----2nd----|        
                          |-----------1st Palindrome---------|
                          min          i'  c   i           max
                          |------------|---|---|-------------|
         --------------------------------------------------------------------
    idx= | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|
         --------------------------------------------------------------------- 
       T=| $ | b | $ | a | $ | b | $ | a | $ | a | $ | b | $ | c | $ | a | $ |
         ---------------------------------------------------------------------
       P=| 0 | 1 | 0 | 3 | 0 | 3 | 0 | 1 | 4 | ? | ? | ? | ? | ? | ? | ? | ? |
         ---------------------------------------------------------------------
   

   Now, question is how to check this case? Note that, due to symmetric property length of segment [min..i'] is equals to the length of segment [i..max]. Also, note that 2nd palindrome is completely within 1st palindrome iff left edge of the 2nd palindrome is inside the left boundary, min of the 1st palindrome. That is,

   
           i'-P[i'] >= min
           =>P[i']-i' < -min (negate)
           =>P[i'] < i'-min 
           =>P[i'] < max-i [(max-i)=(i'-min) due to symmetric property].
   

   Combining all the facts in case 1,

   P[i] = P[i'], iff (max-i) > P[i']

2. If the second palindrome meets or extends beyond the left bound of the first palindrome, then the third palindrome is guaranteed to have at least the length from its own center to the right outermost character of the first palindrome. This length is the same from the center of the second palindrome to the left outermost character of the first palindrome.

   For example in the following figure, second palindrome centered at i=5 extends beyond the left bound of the first palindrome. So, in this case we can't say P[i]=P[i']. But length of the third palindrome centered at i=11, P[i] is at least the length from its center i=11 to the right bound max=12 of first palindrome centered at c. That is, P[i]>=1. This means third palindrome could be extended past max if and only if next immediate character past max matches exactly with the mirrored character, and we continue this check beyond. For example, in this case P[13]!=P[9] and it can't be extended. So, P[i] = 1.

                                                       
                 |-------2nd palindrome------|   |----3rd----|---?    
                          |-----------1st Palindrome---------|
                          min  i'          c           i   max
                          |----|-----------|-----------|-----|
         --------------------------------------------------------------------
    idx= | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|
         --------------------------------------------------------------------- 
       T=| $ | b | $ | a | $ | b | $ | a | $ | a | $ | b | $ | c | $ | a | $ |
         ---------------------------------------------------------------------
       P=| 0 | 1 | 0 | 3 | 0 | 3 | 0 | 1 | 4 | 1 | 0 | ? | ? | ? | ? | ? | ? |
         ---------------------------------------------------------------------
   

   So, how to check this case? This is simply the failed check for case 1. That is, second palindrome will extend past left edge of first palindrome iff,

   
           i'-P[i'] < min
           =>P[i']-i' >= -min [negate]
           =>P[i'] >= i'-min 
           =>P[i'] >= max-i [(max-i)=(i'-min) due to symmetric property]. 
   

   That is, P[i] is at least (max-i) iff (max-i) P[i]>=(max-i), iff (max-i) Now, if the third palindrome does extend beyond max then we need to update the center and the boundary of the new palindrome.

   If the palindrome centered at i does expand past max then we have new (extended) palindrome, hence a new center at c=i. Update max to the rightmost boundary of the new palindrome.

   Combining all the facts in case 1 and case 2, we can come up with a very beautiful little formulae:

   
           Case 1: P[i] = P[i'],  iff (max-i) > P[i']
           Case 2: P[i]>=(max-i), iff (max-i) = min(P[i'], max-i). 
   

   That is, P[i]=min(P[i'], max-i) when the third palindrome is not extendable past max. Otherwise, we have new third palindrome at center at c=i and new max=i+P[i].

3. Ни первый, ни второй палиндром не предоставляют информацию, помогающую определить палиндромную длину четвертого палиндрома, центр которого находится за пределами правой стороны первого палиндрома.

   То есть мы не можем определить заранее P [i] если i> макс. То есть

   P [i] = 0, если max-i & lt 0

   Объединяя все случаи, мы заключаем формулы:

   P [i] = max> i? min (P [i '], max-i): 0. В случае, если мы можем расширить за пределы max, мы расширяем, сопоставляя символы за пределами max с зеркальным символом относительно нового центра в c = i. Наконец, когда у нас есть несоответствие, мы обновляем new max = i + P [i].

Ссылка: описание алгоритма на странице вики

Я снял видео об этом алгоритме с использованием анимационной графики. Надеюсь, это поможет вам понять это! https://www.youtube.com/watch?v=kbUiR5YWUpQ

Этот материал очень помогает мне понять его: http://solutionleetcode.blogspot.com/2013/07/leetcode-longest-palindromic-substring.html

Определите T как длину самой длинной палиндромной подстроки с центром в каждом из символов.

Ключевым моментом является то, что когда меньшие палиндромы полностью встроены в более длинный палиндром, T [i] также должен быть симметричным внутри более длинного палиндрома.

В противном случае нам придется вычислять T [i] с нуля, а не индуцировать из симметричной левой части.

Быстрое решение Javascript для поиска самого длинного палиндрома в строке:

const lpal = str => {
  let lpal = ""; // to store longest palindrome encountered
  let pal = ""; // to store new palindromes found
  let left; // to iterate through left side indices of the character considered to be center of palindrome
  let right; // to iterate through left side indices of the character considered to be center of palindrome
  let j; // to iterate through all characters and considering each to be center of palindrome
  for (let i=0; i<str.length; i++) { // run through all characters considering them center of palindrome
    pal = str[i]; // initializing current palindrome
    j = i; // setting j as index at the center of palindorme
    left = j-1; // taking left index of j
    right = j+1; // taking right index of j
    while (left >= 0 && right < str.length) { // while left and right indices exist
      if(str[left] === str[right]) { //
        pal = str[left] + pal + str[right];
      } else {
        break;
      }
      left--;
      right++;
    }
    if(pal.length > lpal.length) {
      lpal = pal;
    }
    pal = str[i];
    j = i;
    left = j-1;
    right = j+1;
    if(str[j] === str[right]) {
      pal = pal + str[right];
      right++;
      while (left >= 0 && right < str.length) {
        if(str[left] === str[right]) {
          pal = str[left] + pal + str[right];
        } else {
          break;
        }
        left--;
        right++;
      }
      if(pal.length > lpal.length) {
        lpal = pal;
      }
    }
  }
  return lpal;
}

Пример ввода

console.log(lpal("gerngehgbrgregbeuhgurhuygbhsbjsrhfesasdfffdsajkjsrngkjbsrjgrsbjvhbvhbvhsbrfhrsbfsuhbvsuhbvhvbksbrkvkjb"));

Вывод

asdfffdsa

Я пережил то же разочарование / борьбу и нашел решение на этой странице, https://www.hackerearth.com/practice/algorithms/string-algorithm/manachars-algorithm/tutorial/, чтобы облегчить понимание. Я попытался реализовать это решение в своем стиле и, думаю, теперь могу понять алгоритм. Я также попытался набить как можно больше объяснений в коде, чтобы объяснить алгоритм. Надеюсь на эту помощь!

#Manacher's Algorithm
def longestPalindrome(s):
  s = s.lower()
  #Insert special characters, #, between characters
  #Insert another special in the front, $, and at the end, @, of string  to avoid bound checking.
  s1 = '$#'
  for c in s:
      s1 += c + '#'
  s1 = s1+'@'
  #print(s, " -modified into- ", s1)

  #Palin[i] = length of longest palindrome start at center i
  Palin = [0]*len(s1)

  #THE HARD PART: THE MEAT of the ALGO

  #c and r help keeping track of the expanded regions.
  c = r = 0

  for i in range(1,len(s1)-1): #NOTE: this algo always expands around center i

      #if we already expanded past i, we can retrieve partial info 
      #about this location i, by looking at the mirror from left side of center.

      if r > i:  #---nice, we look into memory of the past---
          #look up mirror from left of center c
          mirror = c - (i-c)

          #mirror's largest palindrome = Palin[mirror]

          #case1: if mirror's largest palindrome expands past r, choose r-i
          #case2: if mirror's largest palindrome is contains within r, choose Palin[mirror]
          Palin[i] = min(r-i, Palin[mirror]) 

      #keep expanding around center i
      #NOTE: instead of starting to expand from i-1 and i+1, which is repeated work
      #we start expanding from Palin[i], 
      ##which is, if applicable, updated in previous step
      while s1[i+1+Palin[i]] == s1[i-1-Palin[i]]:
          Palin[i] += 1

      #if expanded past r, update r and c
      if i+Palin[i] > r:
          c = i
          r = i + Palin[i]

  #the easy part: find the max length, remove special characters, and return
  max_center = max_length = 0
  for i in range(len(s1)):
      if Palin[i] > max_length:
          max_length = Palin[i]
          max_center = i  
  output = s1[max_center-max_length : max_center+max_length]
  output = ''.join(output.split('#'))
  return output # for the (the result substring)