[알고리즘] 마나허 (Manacher)

[알고리즘 소개]

전체 문자열에서 회문의 개수 및 길이를 구하는 알고리즘

 

---

[코딩 방법]

1. 현재 시점에서 최대 길이 회문의 인덱스 c, 최대 길이 회문의 최고 인덱스 r, 그리고 i번째를 중심으로 하는 회문의 반지름 P[i]
2. 짝수 회문도 검사하기 위해 문자열 사이사이에 문자 삽입 (ex. abcde → #a#b#c#d#e#)
3. 반복문을 돌면서 i > r 이라면 P[i] = 0,
   else라면 가장 긴 회문 안에 현재 인덱스가 들어 있는 것이므로 대칭인 P'[i]( = P[2 * c - i] )에 대해 P[i] == P'[i]임이 보장됨. 즉, P[i] = P'[i]가 되어야 하지만, r안에 들어와 있어야만 P[i] == P'[i]가 보장되므로 P[i] = min(P'[i], r - i)
4. P[i]의 초기값을 빠르게 구했으므로 이제는 직접 비교하면서 P[i]를 증가.
   while (i + P[i] + 1 < (최대 길이) && i - P[i] - 1 > -1 && s[i + P[i] + 1] == s[i - P[i] - 1]) ++P[i]
5. 과정 4까지 마쳤으면 i를 중심으로 하는 회문의 최대 길이는 i + P[i]이므로 i + P[i] > r이라면 r과 c갱신 필요.
   r = i + P[i], c = i

---

[시간 복잡도]

$O(N)$

 

---

[공부용 링크]

https://blog.naver.com/PostView.nhn?blogId=jqkt15&logNo=222108415284