개발블로그

Manacher's Algorithm은 문자열 내에서 회문(팰린드롬, palindrome)을 찾는 것과 관련된 알고리즘이며, 시간복잡도는 O(N)이다. (여기서 N은 문자열의 길이) 여기서 회문, 팰린드롬이란, 앞뒤를 뒤집어도 똑같은 문자열을 의미한다. 여기서 단순하게 하나하나 문자열을 자르고 뒤집어 비교하는 것은 시간이 오래 걸리기에 효율적이지 못하다. 이 알고리즘은 문자열 S에 대해 다음과 같은 배열을 만들 수 있다. 문자열 S의 길이를 N이라 하고 (|S| = N) 같은 길이의 정수 배열 A를 만든다. A의 i번째 원소 A[i]는 i번째 문자를 중심으로 하는 가장 긴 회문의 반지름 크기이다. (회문의 길이가 5이면, 반지름은 2가 된다) 즉, 부분 문자열 S[i-A[i] , i+A[i]] 는 회문이..