"파이썬으로 구현하는"시리즈 3매내처(Manacher)오늘은 갑자기 뜬금없이 파이썬으로 구현하는 매내처에 대해서 알아볼 것이다.원래는 세그먼트 트리 바텀업을 먼저 적었어야 했는데, 문제풀다가 매내처라는 천재적인 알고리즘을 공부하게 되어서 정리해본다. 먼저 매내처가 뭐하는 알고리즘인지 알아보자.팰린드롬이란 무엇인가?앞뒤가 대칭인 문자열을 팰린드롬이라고 한다. 우리말로 회문이라고 한다.예시로는 다음이 있다. 'bob''ABCBA''WAS IT A CAT I SAW' (이상한 나라의 앨리스에 나오는 유명한 회문)'다시합창합시다' 다음과 같은 예시들은 팰린드롬이 아니다. 'apple''팰린드롬''알고리즘' 매내처는 팰린드롬을 다루는 알고리즘인데, 구체적으로는 다음과 같은 문제를 풀 때 쓰인다. 문자열 S가 주어..
