#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:
На этой странице объясняется алгоритм Манахера и дан ответ на вопрос с помощью визуальной анимации.