문제풀이
팰린드롬을 효율적으로 찾는 매내처 알고리즘
pwerty
2025. 5. 22. 11:25
흔하게 보이는 유형은 아니라고 생각했는데, 의외로 백준에 제법 분량이 있다고 한다. 한번쯤 짚고 가면 좋을 것 같아서 찾고 정리하려고 한다. 알고리즘은 어하지 않아도 되는 계산을 적절한 논리를 통해 넘길 수 있다면 속도적 개선점을 찾을 수 있다. 그에 대해 써 내려가보겠다.
Manacher's Algorithm은 회문을 효율적으로 찾는 알고리즘이다. 우선, 회문의 정의을 아주 간단하게 짚고 가보자.
회문은 팰린드롬과 동의어이다. 앞에서 읽으나 뒤에서 읽으나 같은 문자열이다.
- 기러기 역삼역 우영우 같은 단어들은 회문의 대표적인 예제이다.
핵심
어떤 전체 문자열에서 일부의 팰린드롬을 찾는데는 O(N^2)가 소요될 것이다. 앞 뒷 비교.. 하다보면 제일 빨리 떠올릴 수 있는 방법이 그 정도 시간이 걸린다. 하지만 매내처 알고리즘은 O(N)으로 빠르다. 이에 대한 개선한 원리는 이미 계산된 정보를 통해 중복 계산을 피하는 것.
작동 원리
- 문자열 전처리
- 짝수 길이 팰린드롬을 쉽게 찾기 위해 각 문자 사이에 Dummy를 삽입한다.
- 이것은 실제 코드가 시작하기전 이뤄저야 하는 작업이기 때문에 전처리 작업으로써 필요하다.
for (char cc : s) // 각 문자 하나에 대해
{
ss.push_back('#'); // Dummy 역할을 할 한 글자를 넣고
ss.push_back(cc); // 기존에 입력받았던 s에서의 한글자 단위인 cc를 삽입 시도 하는 것이다.
}
- 반지름 개념을 활용
- 각 위치에서 가능한 팰린드롬의 최대 반지름을 계산한다.
- 이게 기하학적 지식을 쓰는건 아니고, 중심에서 팰린드롬 끝까지의 거리를 사용하는 것이다.
- 중복 계산을 피하기 위한 목적이다. aba 팰린드롬의 반지름은 1이다.
하단의 코드는 방금 전처리 해서 ss에 담긴 모든 문자열에 대해 for문을 돌면서 이루어진다. 즉, 작동 대상은 문자열 내 모든 내용이다.
for(int i = 0; i < ss.size(); i++)
{
// start- 핵심 최적화 기법
- 이전에 발견한 팰린드롬 내에 있는 문자의 경우, 그 문자를 중심으로 하는 팰린드롬은 이미 계산된 대칭 위치의 팰린드롬 정보를 활용한다.
- 예를 들어 "abacaba"에서, c를 중심으로 하는 팰린드롬 안에 있는 두 번째 a를 탐색하기 전 첫 번째의 a의 정보를 활용한다.
if (i <= r) // i는 for문을 돌면서 지정되는 인덱스이다. 이전에 발견된 팰린드롬 내부에 있는지 부터 본다.
{
// 해당 된다면 i <= r, 대칭 위치의 반지름 정보를 활용한다.
mana[i] = min(r - i, mana[c + (c - i)]);
// min을 사용해서 대칭점의 반지름이 현재 알려진 팰린드롬 경계를 넘지 않도록 보정한다.
}
- 탐색 범위 확장
- 이미 알려진 반지름부터 시작해 양쪽으로 문자를 비교하며 팰린드롬 길이를 확장한다.
- 새로 발견한 더 큰 팰린드롬이 있으면 중심점과 반지름 정보를 갱신한다.
while (i + mana[i] + 1 < ss.size() and i - mana[i] - 1 >= 0 and ss[i + mana[i] + 1] == ss[i - mana[i] - 1])
{
++mana[i];
}
// i + mana[i] + 1과 i - mana[i] - 1은 다음에 비교할 문자 위치를 가리킨다.
// 문자열 범위를 벗어나지 않고 AND 양쪽 문자가 동일 할 때 반지름, mana[i]를 증가시킨다.
// 이 과정을 통해 각 위치에서 간으한 최대 팰린드롬 길이를 찾을 수 있게 되었다.
그리고 필요하다면 갱신해줘야한다!
if (i + mana[i] > r) // 현재 위치에서 발견한 팰린드롬이 이전에 알려진 경계보다 더 우측으로 확장 시..
{
c = i; // 중심점 c를 현재 위치 i로 갱신한다.
r = i + mana[i]; // 오른쪽 경계 r을 새롭게 발견된 팰린드롬의 오른쪽 끝으로 갱신한다.
} // 이 정보는 다음 위치 처리 시 최적화에 활용 할 수 있다.} // 반복문 종료
https://www.acmicpc.net/problem/16163
이 문제를 해결 할 수 있게 되었다. 축가한다!
#include <iostream>
#include <string>
using namespace std;
string s;
string ss;
int mana[4000005];
int r = -1;
int c = -1;
void solve()
{
cin >> s;
for (char cc : s)
{
ss.push_back('#');
ss.push_back(cc);
}
ss.push_back('#');
for (int i = 0; i < ss.size(); i++)
{
if (i <= r)
{
mana[i] = min(r - i, mana[c + (c - i)]);
}
while (i + mana[i] + 1 < ss.size() and i - mana[i] - 1 >= 0 and ss[i + mana[i] + 1] == ss[i - mana[i] - 1])
{
++mana[i];
}
if (i + mana[i] > r)
{
c = i;
r = i + mana[i];
}
}
}
int main() {
long long result = 0;
solve();
for(int i = 0; i < 4000005; i++)
{
result += (mana[i] + 1) / 2;
}
cout << result << '\n';
return 0;
}