테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== ABB ======

===== 풀이 =====
  * 문자열의 suffix중에서 팰린드롬을 이루는 가장 긴 suffix를 찾으면 된다. 그러면 {문자열의 길이} - {가장 긴 팰린드롬 suffix의 길이} 만큼의 글자를 추가해서 전체를 팰린드롬으로 만들어 줄 수 있다.
  * [[ps:가장 긴 팰린드롬 부분문자열|Manacher's algorithm]]을 돌리고 나면, 각 부분문자열의 팰린드롬 여부를 O(1)에 확인할수 있으므로 n개의 suffix들에 대해서 팰린드롬 여부를 모두 체크해서 가장 긴 것을 찾으면 된다. 시간복잡도는 O(1)
  * 사실 이 작업은 해싱으로 구하는 것이 로직도 더 간단하고 메모리도 적게 먹을것 같지만, 어차피 시간복잡도는 똑같이 O(n)이 들기 때문에 굳이 구현하지는 않았다. Manacher's algorithm 은 이미 구현된 것([[:ps:teflib:string#palindrome_radiuses|teflib.string.palindrome_radiuses]])을 사용하면 되지만, 이 방법은 새로 코드를 짜야 하기 때문에 귀찮..

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 18171. ABB".

- Problem link: https://www.acmicpc.net/problem/18171
- Solution link: http://www.teferi.net/ps/problems/boj/18171

Tags: [Manacher]
"""

from teflib import string


def main():
    N = int(input()) 
    colors = input()
    
    radiuses = string.palindrome_radiuses(f"#{'#'.join(colors)}#")
    right_end = N * 2
    max_rad = max(r for c, r in enumerate(radiuses) if c + r == right_end)
    
    print(N - max_rad)
    

if __name__ == '__main__':
    main()

</dkpr>
  * Dependency: [[:ps:teflib:string#palindrome_radiuses|teflib.string.palindrome_radiuses]]

{{tag>BOJ ps:problems:boj:플래티넘_4}}