[백준 14444] 가장 긴 팰린드롬 부분 문자열 (python)

https://www.acmicpc.net/problem/14444

14444번: 가장 긴 팰린드롬 부분 문자열

가장 긴 팰린드롬 부분 문자열 문제

문자열 S의 부분 문자열 중에 가장 길이가 긴 회문을 구하는 문제

Manacher 알고리즘을 이용하여 해결할 수 있었다.

https://www.acmicpc.net/problem/13275

13275번: 가장 긴 팰린드롬 부분 문자열

백준 13275번 문제와 동일한 문제지만, 시간제한이 13275번 문제와 다르게 2초로 주어졌다.

상대적으로 시간적 여유가 널럴하므로, 최대한 알고리즘 그대로 구현하였다.

 

📌문제 접근 포인트

1. 회문의 부분 문자열의 크기를 구하기 위해서 다이나믹 프로그래밍을 이용할 수 있지만, 시간 복잡도는 O(n²) 이므로 더 빠른 방법을 생각해 보자.
2.. 회문의 부분 문자열의 크기를 구하는 알고리즘 중에서 Manacher 알고리즘을 이용하면 시간 복잡도 O(n)으로 계산할 수 있다. (모른다면 아래 링크내용 참고)
3. 정직하게 Manacher 알고리즘 방식 그대로 구현해서 (불필요한 부분을 제거하지 않아서) 시간이 좀 늘어났지만, 시간 안에 풀 수 있었다.

https://edder773.tistory.com/178

[알고리즘] Manacher 알고리즘 정리 (python)

⚙ 내가 푼 정답 코드

def manachers(S, N):
    A = [0] * N
    r, p = 0, 0
    for i in range(N):
        if i <= r:
            A[i] = min(A[2 * p - i], r - i)
        while i - A[i] - 1 >= 0 and i + A[i] + 1 < N and S[i - A[i] - 1] == S[i + A[i] + 1]:
            A[i] += 1
        if r < i + A[i]:
            r = i + A[i]
            p = i
    return A

import sys
S = sys.stdin.readline()
N = len(S)
s = ""
for i in range(N):
    s += '#'
    s += S[i]
s += '#'
A = manachers(s, len(s))
print(max(A))