Manacher

길이가 \(n\)인 문자열 \(S\)가 있습니다.

이 문자열의 부분 문자열 중 팰린드롬인 것을 모두 알고 싶다면, 어떻게 하면 될까요?

 

나이브하게 \(O(n^3)\) 또는 \(O(n^2)\)로도 해결할 수 있겠지만,

이를 \(O(n)\)에 해결할 수 있는 Manacher 알고리즘에 대해 알아봅시다.

 

\(S\)의 각 \(i\)번째 문자를 중심으로 하는 팰린드롬의 최대 반지름을 \(A_i\)라고 정의합시다.

또, \(j < i\)인 모든 \(j\)에 대해, \(j + A_j\)의 최대값을 \(m\)라고 하고, 그 때의 \(j\)를 \(k\)라고 합시다.

이제 각 인덱스 \(i\)에 대해 \(A_i\)의 값을 계산해 채워봅시다.

 

다음과 같이 케이스를 나눌 수 있습니다.

 

1. \(i > m\)
현재 얻을 수 있는 정보가 없으므로, \(A_i\)를 직접 1씩 증가시키면서 답을 계산합니다.
\(m = i + A_i\)가 됩니다.

2. \(i \le m\)
현재 인덱스 \(i\)는 \(k\)번 인덱스를 중심으로 하는 팰린드롬의 내부에 속합니다.
이 팰린드롬에서 \(i\)번 인덱스와 대칭되는 인덱스를 \(i'\)이라고 한다면,
\(i\)번 인덱스에서 팰린드롬의 크기 \(A_i\)는 최소 \(\min(m-i, A_{i'})\)임을 알 수 있습니다.
\(i'\)는 \(k\)를 이용해 구할 수 있습니다.

2.1 \(m-i \ge A_{i'}\)
\(A_i = A_{i'}\) 입니다. \(m\)의 값은 변하지 않습니다.

2.2 \(m-i < A_{i'}\)
\(A_i\)의 값이 더 커질 가능성이 있으므로, \(A_i\)의 값을 \(A_{i'}\)부터 시작해 직접 1씩 증가시면서 답을 계산합니다.
\(m = i+A_i\)가 됩니다.

반복문을 도는동안 \(m\)는 총 \(n\)번 증가하므로, 총 시간복잡도 역시 \(O(n)\)입니다.

 

 

짝수 팰린드롬의 경우, 문자 사이사이에 문자열에 존재하지 않는 임의의 문자를 넣어 계산함으로써 해결할 수 있습니다.

ex) abba -> $a$b$b$a$ 로 치환후 Manacher 알고리즘 사용

 

www.acmicpc.net/problem/16163

16163번: #15164번_제보

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
const int N = 4000005;
string s = "$";
int A[N];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    string tmp; cin >> tmp;
    for (char c : tmp)
    {
        s.push_back(c);
        s.push_back('$');
    }
 
    int m = -1, k = -1;
 
    ll ans = 0;
    for (int i = 0; i < s.size(); i++)
    {
        if (i <= m) A[i] = min(m - i, A[2 * k - i]);
 
        while (0 <= i - A[i] - 1 && i + A[i] + 1 < s.size()
            && s[i - A[i] - 1] == s[i + A[i] + 1])
        {
            if (i + ++A[i] > m) m = i + A[i], k = i;
        }
 
        ans += (A[i] + 1) / 2;
    }
 
    cout << ans;
}

---

제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.

 

www.acmicpc.net/group/7712

ANZ1217