전체 문자열에서 palindrome의 갯수 세기; O(N)
Manacher, Glenn이 1975년에 발표한 논문에 실렸던 알고리즘이다. 전체 문자열의 부분 문자열에서 palindrome의 갯수를 세고 그 위치 또한 알 수 있다.먼저 문자 사이사이에 # 등을 삽입한다. 이렇게 하면 palindrome의 홀짝(aba, abba)을 따질 필요가 없기 때문이다. abacada를 #a#b#a#c#a#d#a# 로 바꾸는것. 알고리즘은 현재까지 찾은 palindrome 중 right bound(오른쪽 끝)이 가장 오른쪽에 있는 palindrome을 저장하며 진행한다. 또한 dp table을 채워나가는데, dp[i]는 i번째 문자를 기준으로 하는 가장 긴 palindrome의 길이의 절반이다.예)abacada: # a # b # a # c # a # d # a # 0 1 0..
2015. 6. 10. 02:19