PS 이야기

Manacher's Algorithm은 문자열 내에서 회문(팰린드롬, palindrome)을 찾는 것과 관련된 알고리즘이며, 시간복잡도는 $O(N)$이다. (여기서 $N$은 문자열의 길이) 이 알고리즘은 문자열 $S$에 대해 아래와 같은 배열을 구할 수 있다.문자열 $S$의 길이, $|S| = N$과 같은 길이의 정수 배열 $A$$A$의 $i$번째 원소 $A[i]$는 $i$번째 문자를 중심으로 하는 가장 긴 회문의 반지름 크기 (회문의 길이가 5이면, 반지름은 2가 됨)즉, 부분 문자열 $S[i-A[i] ~ i+A[i]]$는 회문이며, $S[i-A[i]-1 ~ i+A[i]+1]$은 회문이 아니다. 예를 들어, "banana"라는 문자열 $S$에 대한 배열 $A$는 아래와 같다. $S$ b a n a n ..