動機

Manacher

先在每個字之間插一字元，可以把它看成mirror另一半過來 同時處理回文有兩個case(奇數長度、偶數長度)要看的問題，因為現在任何迴文都是奇數長度

所以變成可以只追蹤一邊的長度就好，因此m[i]定義為迴文延伸出去的距離

這樣就與z algorithm很像

  1. 確認現在要看的回文中心，是不是在目前已確認的範圍中，如果有就先抄答案
  2. 開始延伸回文長度
  3. 如果延伸後的範圍比現在的大就更新範圍
def f(s):
	magic = f'{"".join(["".join(n) for n in zip("#"*(len(s)+1), s)])}#'
	m = [0]*len(magic)

	def canExtend(i):
		left, right = i-m[i]-1, i+m[i]+1
		isLegalIdx = 0 <= left and right < len(magic)
		return isLegalIdx and magic[left] == magic[right]

	C, R = 0, 0
	for i in range(len(magic)):
		# mirror ... C ... i ... R
		# 只要是在範圍內就是對成就可以直接拿前面的來用
		# mirror .. (C+(C-i) .. C) is part of Palindrom
		# mirror'Left .. Left .. (mirror .. R').. C .. (i ~ R) is part of Palindrom
		if i < R:
			m[i] = min(R-i, m[C+(C-i)])
		while canExtend(i):
			m[i]+=1
		if i+m[i] > R:
			C, R = i, i+m[i]
	i, l = max(enumerate(m), key=lambda x: x[1])
	# [i-l ~ i+l] is # a # ... a #
	return ''.join(c for c in magic[i-l:i+l+1] if c != "#")

print(f("babbad"))

Ref