가장 긴 팰린드롬 부분문자열 (Longest Palindromic Substring)

Longest palindromic substring 을 참고.
- 사실 이 문서에서의 메인 주제는 '가장 긴 팰린드롬 부분문자열' 이라는 태스크가 아니라, Manacher's algorithm에 관한 전반적인 내용이다.
그냥 단순한 DP로 풀려고 하면 O(n^2)이다
하지만 Manacher's algorithm 이라는 O(n) 알고리즘이 존재하다.
- 발상은 신선한데, 발상만 들으면 이해하기도 쉽고 코드도 간단하게 짤수 있다. 시간복잡도가 O(n)이 되는 것을 설명하는 것은 조금 더 어렵지만 그래도 쉬운편.
Manacher's algorithm 은 문자열의 각 문자들에 대해서, 그 문자를 중심으로 하는 팰린드롬의 최대 길이를 구해준다. 이것은 가장 긴 팰린드롬 부분문자열을 구하는 용도 외에도 여러가지로 사용될 수 있다
- 어떤 부분문자열이 팰린드롬인지 O(1)에 확인하기
- 모든 부분문자열중 팰린드롬인 것의 갯수 구하기
- 길이가 k인 부분문자열 팰린드롬 모두 찾기
- 등등.. (이중에서는 해싱으로도 풀 수 있는 것들도 있다)

구현

Manacher's algorithm의 구현
- teflib.string.palindrome_radiuses
Manacher's algorithm은 홀수 길이 팰린드롬만 처리할 수 있다. 짝수 길이 팰린드롬도 구하기 위해서는, 알고리즘을 돌리기 위해 원본 문자열을 수정해서 돌리는 것이 기본 테크닉이다. 각 글자 사이에 특수 문자를 삽입해서 “book”를 “#b#o#o#k”와 같은식으로 변형해서 돌리면, 짝수길이 팰린드롬인 “oo”가 홀수길이 팰린드롬 “#o#o#“처럼 바뀌므로 처리가 가능하게 된다.
하지만 이렇게 문자열을 변형해서 돌렸을 경우, 원본 스트링에 대한 결과를 얻으려면 다시 약간의 처리를 해줘야 한다. 보통은 단순하지만, 신경쓰기 번거러울 경우가 있다.
그래서, 짝수 길이 팰린드롬만 처리할수 있도록 코드를 약간 변형했다. 추가 인자를 받아서, 거기에 따라서 홀수 길이 팰린드롬의 반경을 구할지, 짝수 길이 팰린드롬의 반경을 구할지 동작이 달라지는 것이다. 실제로 두가지 방법의 구현은 거의 유사하다. 실행시간 면에서는 문자열을 수정해서 홀수길이 팰린드롬을 처리하는 방법이나, 문자열을 수정않고 홀수길이와 짝수길이 팰린드롬에 대해서 두번 함수를 호출하는 것이나 큰 차이는 없었다. 문제에 따라서 이해하기 쉬운걸로 사용하자.

가장 긴 팰린드롬 부분문자열을 찾을 때는 다음처럼 사용하면 된다. 위에 설명한 두가지 방법을 모두 적었다.

def length_of_longest_palindromic_substring(s):
    return max(string.palindrome_radiuses(f"#{'#'.join(S)}#"))

def length_of_longest_palindromic_substring(s):
    return max(max(palindrome_radiuses(S, is_for_odd_len=True)) * 2 + 1,
               max(palindrome_radiuses(S, is_for_odd_len=False)) * 2)

문자열 S[beg:end]가 팰린드롬인지 확인하려면

radiuses = palindrome_radiuses(f"#{'#'.join(S)}#")

def is_palindrome(beg, end, radiuses):
    center = beg + end
    return end - beg - 1 <= radiuses[center]

여러 문제들을 teflib.string.palindrome_radiuses v1.0 구현을 이용해서 풀었는데, 뒤는게 구현에 버그가 있었던 것을 알게 되었다. 버그에도 불구하고 AC를 받았던 이유는 #을 넣어서 문자열을 변형한 경우에는 문제없이 돌아가기 때문.. 어쨌든 버그를 확인했으니 고쳐서 v1.1을 만들었는데 이렇게 되자 코드 실행속도가 더 느려졌다. 버그를 수정한 코드가 기존에 올라간 코드를 밀어냈으면 좋겠는데 그게 안된다. v1.0으로 제출해서 맞은 코드는 그냥 우선 다 비공개처리를 해버렸다.

목차

가장 긴 팰린드롬 부분문자열 (Longest Palindromic Substring)

구현

관련 문제