일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
- bfs
- 분할정복
- 비트마스킹
- 결정 문제
- 결정문제
- 구현
- 이분탐색
- 서로소 집합
- parametric search
- 깊이 우선 탐색
- 백준 1464
- 최장증가수열
- Lis
- 백준 뒤집기 3
- 최장길이바이토닉수열
- 재귀
- disjoint set
- DP
- 그래프이론
- 이분 탐색
- 그래프탐색
- 브루트포스
- 2493 백준
- 패스트캠퍼스
- 뒤집기 3
- boj 1464
- union find
- 1939백준
- 그래프 탐색
- 그래프 이론
- Today
- Total
알고리즘 문제풀이
Manacher 알고리즘 본문
1975년에 발표된 Manacher 알고리즘은 "특정 문자를 중심으로 하는 팰린드롬 중 가장 긴 홀수 팰린드롬의 길이"를 찾는 알고리즘이다.
Manacher알고리즘은 Polynomial time을 가지는 문자열 알고리즘과 동일하게 "이미 탐색한 것에 대해서는 다시 돌아보지 않는다는 측면"에서 맥이 같다고 볼 수 있다.
Manacher알고리즘은 팰린드롬에서 가지는 대칭성을 이용하여 이전에 한번 탐색한 구간에 대해서 이전에 구했던 정보를 활용한다.
예를 들어서 다음과 같은 경우가 있을 것이다. 여기서 [L, R]은 이전까지 탐색했던 범위라고 가정을 하자.
즉 j < i 인 j 에 대하여, 이미 j번째에서 [L,R] 구간까지 탐색을 완료했다는 뜻이 된다.
그리고 현재, 우리는 i번째 문자에 대하여 "i번째 문자를 중심으로 하는 팰린드롬 중 가장 긴 홀수 팰린드롬의 길이의 절반" 을 찾고싶다.
{ 이것을 dp[i] 라고 정의하자, "i를 중심으로 한 가장 긴 홀수 팰린드롬의 길이"를 x라 한다면 i = (x+1)/2 가 된다. }
홀수 길이의 팰린드롬의 길이의 절반은 float로 떨어지게 되고, 이를 처리하기 위해서 내림/올림 처리를 해주어야하는데
올림 처리를 하여서 길이가 1인 팰린드롬도 직관적으로 표현하였다.
이것을 표현한 그림은 다음과 같다.
이것을 통해 무엇을 알 수 있을까?
중심점(=대칭점)인 j에 대하여 i와 대칭인 점 i'을 생각해보도록 하자.
[L,R]구간내에서 팰린드롬을 만족할 때 팰린드롬의 대칭성에 대한 성질에 따라,
S[i'] = S[i] 이고 또한 S[i' - k] = S[i + k] {단, i' - k >= L and i + k <= R} 인 것을 알 수 있다.
그렇다면, i를 중심으로 하는 홀수개의 팰린드롬의 최대 인덱스가 R범위 내에만 있다면 i'에서 구한 i'를 중심으로 하는 홀수개의 팰린드롬의 개수와 동일하다는 의미가 되므로 뒤를 살펴볼 필요없이 해당 값을 재활용하면 된다는 것을 의미한다.
즉, 위와 같은 상황 일 경우 이전의 정보를 그대로 활용하여 불필요한 탐색을 줄일 수 있다.
그렇지 않은 경우, 우리는 Naive하게 탐색을 진행 해주어야한다.
자 여기까지 기본적인 원리에 대하여 알아보았다.
보다 더 자세한 설명을 위해 정의를 살펴보고 가자.
1. dp[i] : i를 중심으로 하는 가장 긴 홀수 팰린드롬의 길이를 x라 하였을 때, (x+1)/2
즉 대칭점을 포함한 오른쪽 구간의 길이 (dp[i])
2. 0 <= i < N 순서대로 dp table을 채워나간다.
3. 0 <= j < i 인 j중 j+dp[j]가 max가 되는 j를 p라고 가정하고
이 때, 팰린드롬의 범위[ p - dp[i] + 1, p + dp[j] - 1 ] 을 [ L, R ] 이라고 칭한다.
- 대칭성을 이용할 수 있을 때
- 추가적인 탐색이 필요 없는 경우
- 추가적인 탐색이 필요한 경우
- 대칭성을 이용할 수 없을 때
Case 1-1 ) 대칭성 이용 O , 추가적인 탐색이 필요 없는 경우 { i < R && i + dp[i'] <= R }
앞에서 설명한 대로 dp[i] = dp[i'] 가 된다.
홀수 크기의 구간에 대해서 대칭점(cp)를 하나로 잡을 수 있다.
i' = cp - ( i - cp ) 와 같고 cp = ( L + R ) / 2 이므로, i' = L+R-i 가 된다.
if( i <= R && i + dp[L+R-i] <= R )
dp[i] = dp[L+R-i];
Case 1-2) 대칭성 이용 O, 추가적인 탐색이 필요한 경우 { i < R && i + dp[i'] > R }
다음과 같이 이전까지 탐색한 구간 [oldL, oldR] 범위를 넘어가는 경우 해당 범위 밖을 벗어나는 범위에 대해서는 대칭성을 보장하지 않는다.
그러므로 oldR 범위부터 한칸 씩 크기를 늘려가며 Naive하게 탐색하는 과정이 필요하다.
if( i < R && i + dp[L+R-i] > R ){
int sz = r - i + 1; // size
while( i - sz >= 0 && i + sz < n && S[i-sz] == S[i+sz] )
sz += 1;
dp[i] = sz--;
if( i + sz > r ){
l = i - sz;
r = i + sz;
}
}
커버할 수 있는 구간의 범위가 바뀌었으므로, 구간[L,R]을 갱신하는 과정도 필요하다.
Case 2) 대칭성을 이용할 수 없을 때 ( i > R )
이 경우도 Naive 하게 탐색하는 과정이 필요하다.
if( i > R ){
int sz = 1;
while( i - sz >= 0 && i + sz < n && S[i-sz] == S[i+sz] )
sz += 1;
dp[i] = sz--;
if( i + sz > r ){
l = i - sz;
r = i + sz;
}
}
전체코드
#include <bits/stdc++.h>
using namespace std;
int n;
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
string S;
cin >> S;
n = S.size();
vector<int> odd_dp(n);
int l = 0, r = -1;
// 홀수 크기의 팰린드롬에 대하여 고려
for(int i=0; i<n; i++){
int sz = ( i > r ) ? 1 : min(r-i+1, odd_dp[l+r-i]);
while( i - sz >= 0 && i + sz < n && S[i-sz] == S[i+sz] )
sz += 1;
odd_dp[i] = sz--;
if( i + sz > r ){
l = i - sz;
r = i + sz;
}
}
return 0;
}
Naive 한 Manacher 알고리즘은 대칭점(cp)를 하나로 잡고 양옆으로 1개씩 확장시켜나가는 구조를 가지기 때문에, 짝수 길이의 팰린드롬은 고려해 줄 수 없다. 짝수 길이의 팰린드롬은 대칭점(cp)를 2개로 잡는 것을 통해 해결 할 수 있다.
짝수 길이의 팰린드롬에 대하여 고려한 코드는 다음과 같다.
for(int i=0; i<n; i++){
int sz = ( i > r ) ? 0 : min(r-i+1, even_dp[l+r-i-1]);
while( i - sz - 1 >= 0 && i + sz < n && S[i-sz-1] == S[i+sz] )
sz += 1;
even_dp[i] = sz--;
if( i + sz > r ){
l = i - sz - 1;
r = i + sz;
}
}
cp1-i, cp2+i 로 확장 해 나가면서 Naive하게 탐색하기 때문에 인덱스 범위에 유의하자.
'자료구조 + 알고리즘 > 기초' 카테고리의 다른 글
최소 공통 조상(Lowest Common Ancestor, LCA) 알고리즘 (0) | 2021.08.16 |
---|---|
Trie(트라이) 자료구조 (0) | 2021.08.10 |
CCW(Counter-Clockwise) 알고리즘 (0) | 2021.02.06 |
서로소 집합 ( Disjoint Set Unit ) 자료구조 (0) | 2020.12.12 |
삽입정렬( Insertion sort ) (0) | 2020.11.11 |