(Python/플5)백준알고리즘 13275번: 가장 긴 팰린드롬 부분 문자열, Manacher's 알고리즘

 

문제 바로가기 

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

 

문제:

문자열 S의 부분 문자열 중에서 팰린드롬인 것 중 가장 긴 것의 길이를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있으며 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

출력:

가장 긴 팰린드롬 부분 문자열의 길이를 출력한다.

 

풀이:

 

 

 

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

def solution(s):
    string = ['#']
    for i in range(len(s)):
        string.append(s[i])
        string.append('#')
    # 홀 수 갯수로 만들어준다.
    answer = manachers(string, len(string))
    return answer


def manachers(S, N):
    A = [0] * N
    # 확정된 오른쪽 끝과, 중심
    r, p = 0, 0
    for i in range(N):  #
        if i <= r:
            # i의 대칭점 찾기 / r-i: 자신이 속한 팰린드롬까지의 길이
            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
        #  팰린드롬의 오른쪽 끝이 현재까지 발견된 가장 큰 팰린드롬의 오른쪽 끝보다 더 오른쪽에 있는지 확인
        #  맞다면 오른쪽 중심 바꿔주고, 시작지점 바꿔준다.
        print("시작점 i:" , i, "중심 p:", p, "오른쪾 r:", r,"대칭점 :", "A[i] :",A[i])
        if r < i + A[i]:
            r = i + A[i]
            p = i
    return max(A)

print(solution(input()))

 

 

 

도움되는 블로그, 영상

 

https://www.youtube.com/watch?v=OLpy_Mh6NZY&t=1s

https://ialy1595.github.io/post/manacher/
https://m.blog.naver.com/jqkt15/222108415284