Manacher Algorithm

aabcc라는 문자열이 있다고 가정해보자.

#a#a#b#c#c# 의 문자열의 팰린드롬을 검사한다.

각 알파벳에서 앞뒤의 문자가 같으면 count를 올려준다.

배열에는 각 알파벳이 가지는 펠린드롬 길이를 저장한다.

import sys
input = sys.stdin.readline
# https://www.crocus.co.kr/1075

def manacher(s):
    N = len(s)
    pal = [0 for _ in range(N)]
    center = 0 # 중심점
    long = 0 # 펠린드롬 값
    total = 0 # 총 펠린드롬 갯수

    for cur in range(N): # cur을 중심으로 펠린드롬 만들기
        if s[cur] != "#": # "#" 이 아니면 스스로도 펠린드롬이다.
            total += 1
        if long < cur: 
            pal[cur] = 0
        else:
            pal[cur] = min(pal[2*center - cur], long - cur)
            total += pal[cur] // 2 # aabcc -> aabcc, abc 펠린드롬이다.

        while cur - pal[cur] - 1 >= 0 and cur + pal[cur] + 1 < N and \
            s[cur-pal[cur]-1] == s[cur+pal[cur]+1]: # 앞 뒤 문자가 같으면
            pal[cur] += 1 # pal값 + 1
            if s[cur + pal[cur]] != "#":
                total += 1

        if long < cur + pal[cur]:
            long = cur + pal[cur]
            center = cur
    return total

print(manacher('#' + '#'.join(input()[:-1]) +'#')) # abc -> #a#b#c#