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

 

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

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

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

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

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

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

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

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

상대적으로 시간적 여유가 부족하므로, 최대한 불필요한 반복 연산 등을 제거하여 구현하였다.

 

📌문제 접근 포인트

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 = "#"+"#".join(sys.stdin.readline())+"#"
N = len(S)
A = manachers(S, N)
print(max(A))