마나커1 마나커 (팰린드롬) 길이가 홀수인 문자열 s에 대해 다음을 O(n)에 구할 수 있다. 길이가 짝수인 문자열은 중간에 더미문자를 추가해준다. dp[i] : s[i]를 중심으로 하는 가장 긴 팰린드롬의 반지름 (예를들어, s : aba -> dp : 0 1 0) n = s.size() i : [0~n-1] 순서대로 초기화 할 것. 0~i-1까지 팰린드롬 중 가장 우측의 오른쪽 경계 r과 그때의 인덱스 k을 이용해서 dp[i]초기화 다음과같이 경우를 나누어 초기화해 준다. 1) i p= 2*k-i) 1-1) p를 중심으로 하는 가장 긴 팰린드롬이 k를 중심으로 하는 가장 긴 팰린드롬에 속하는 경우 dp[i] = dp[p] 1-2) p를 중심으로 하는 가장 긴 팰린드롬이 k를 중심으로 하는 가장 긴 팰린드롬의 왼쪽으로 경계를 넘는.. 2020. 3. 20. 이전 1 다음