ABB

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

"""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()

• Dependency: teflib.string.palindrome_radiuses