[백준 16163] #15164번_제보 (python)

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

16163번: #15164번_제보

 

#15164번_제보 문제

문자열 중에 회문인 것의 개수를 구하는 문제

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

 

Manacher 알고리즘에 대한 개념은 아래 링크 참고

https://edder773.tistory.com/178

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

📌 문제 접근 포인트

1. 회문의 부분 문자열 개수를 구하기 위해서 다이나믹 프로그래밍을 이용할 수 있지만, 시간 복잡도는 O(n²) 이므로 더 빠른 방법을 생각해 보자.
2.  회문의 부분 문자열의 크기를 구하는 알고리즘 중에서 Manacher 알고리즘을 이용하면 시간 복잡도 O(n)으로 계산할 수 있다.
3. 매니처 알고리즘을 이용하면 각 칸의 회문의 개수를 알 수 있는데,  이때 구한 A 배열의 각 요소는 해당 지점에서 이루는 회문의 길이를 의미하므로, 그 길이의 절반을 올림 한 숫자가 그 지점에서의 회문 개수임을 알 수 있다.
4. 회문 개수들의 합을 구해서 출력하면 된다. 

⚙️ 내가 푼 정답 코드

def manachers(S):
    N = len(S)
    A = [0] * N
    r, p, result = 0, 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
        result += (A[i]+1)//2 # 각 자리별 회문 개수
    return result

import sys
S = "#"+"#".join(sys.stdin.readline().strip())+"#"
print(manachers(S))