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