Каким образом начальная длина палиндрома с индексом i равна R — i в «алгоритме Манахера»?

#algorithm #substring #palindrome

#алгоритм #подстрока #палиндром

Вопрос:

Я изучаю алгоритм Манахера для решения проблемы с самой длинной палиндромной подстрокой, и я понимаю, что это использует тот факт, что если i’ является центром палиндрома, то будет палиндром с центром в i .

Вместо расширения с нуля мы сохраняем массив P, чтобы отслеживать длину центра палиндромов в точке i по мере продвижения. Мой вопрос в том, как мы узнаем, что будет палиндром размера R-i, если палиндром в зеркале меньше?

Это код для этого.

     def longestPalindrome(self, s):
        # Transform S into T.
        # For example, S = "abba", T = "^#a#b#b#a#$".
        # ^ and $ signs are sentinels appended to each end to avoid bounds checking
        T = '#'.join('^{}$'.format(s))
        n = len(T)
        P = [0] * n
        C = R = 0
        for i in range (1, n-1):

            if (R > i):
               # WHY R-i, how do we know there will be palindrome of size R -i
                P[i] =  min(R - i, P[2*C - i]) 

            # Attempt to expand palindrome centered at i
            while T[i   1   P[i]] == T[i - 1 - P[i]]:
                P[i]  = 1

            # If palindrome centered at i expand past R,
            # adjust center based on expanded palindrome.
            if i   P[i] > R:
                C, R = i, i   P[i]

        # Find the maximum element in P.
        maxLen, centerIndex = max((n, i) for i, n in enumerate(P))    
        return s[(centerIndex  - maxLen)//2: (centerIndex    maxLen)//2]
  

все примеры, которые я нашел, похожи

 a # b # a # b # b # a # b # a
   i'          C         i    
  

Я понимаю, что в этом случае в i есть подпалиндромы, но как насчет таких случаев, как

 a # b # c # d # d # c # b # a
   i'          C         i    
  

Откуда мы знаем, что P [i] будет либо R-i, либо палиндромом в mirror?

Ответ №1:

На этой странице объясняется алгоритм Манахера и дан ответ на вопрос с помощью визуальной анимации.

Визуальное объяснение алгоритма Манахера