알고스팟) COUNTPALIN

https://algospot.com/judge/problem/read/COUNTPALIN

\( 1\leq{N}\leq{10^6} \)

길이가 N인 문자열 S가 입력으로 주어질 때 팰린드롬인 모든 부분 문자열의 개수를 구하는 문제이다.

이 문제를 푸는 방법은 우선 각 중심마다 최대 팰린드롬의 길이를 구한뒤 그 길이/2 만큼을 모두 더해주는 것이다.

왜냐하면 어떤 중심에서 최대 길이의 팰린드롬이 abccba 라면 같은 중심을 가지는 팰린드롬들은 반지름을 1씩 줄여나가면

모두 팰린드롬이기 때문에다. 이것은 자명하다. 즉, abccba, bccb, cc 이게 다 팰린드롬이 되기 때문에 최대팰린드롬길이/2

의 식이 나오는 것이다. 그리고 중심이 다르면 다른 팰린드롬이라는 것이 자명하기 때문에 모든 각각의 중심에 대해

최대 팰린드롬의 길이를 구하기만 하면 되는 것이다. 그런데 N제한이 크기 때문에 일반적인 O(N^2) 의 방법으로

이것을 계산할 수가 없다. 그렇기 때문에 마나처 알고리즘(Manacher's Algorithm) 을 사용하여 O(N)에 계산하여야 한다.

마나처 알고리즘의 설명은  여기 를 참고하면 된다. 반지름이 짝수인 팰린드롬도 모두 고려하기 위해서는

문자열 사이사이에 # 이나 $ 같은 더미문자를 넣어주어야한다. 이 때 유의해야 할 것은 문자열 aa 는

#a#a# 가 되어 양끝에 #까지 계산된다는 것을 잊지않아야 하는것이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3c3c3c3c;
const long long infl = 0x3c3c3c3c3c3c3c3c;
 
int T,N;
string str;
int A[2000005];
int main() {
    cin >> T;
    while(T--){
        str = '~';
        string s;
        cin >> N >> s;
        for(int i = 1 ; i <= N; i++){
            str += '#';
            str += s[i-1];
        }
        str += '#';
        str += '!';
        int R = -1, p;
        for(int i = 1 ; i < str.size()-1; i++){
            if(i <= R) A[i] = min(A[2*p -i], R - i);
            else A[i] = 0;
            while(str[i - A[i] - 1] == str[i + A[i] + 1]) A[i]++;
            if(R < A[i] + i) R = A[i] + i, p = i;
        }
        ll ans = 0;
        for(int i = 1; i < str.size()-1; i++) ans += A[i]/2;
 
        cout << ans << endl;
    }
    return 0;
}