[BOJ 18171 // C++] ABB

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 18171번 문제인 ABB이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/18171

18171번: ABB

문제를 간단히 요약하면, 입력으로 첫 줄에 1 이상 40만 이하의 정수 N을 주고, 둘째 줄에 알파벳 소문자로 이루어진 길이 N의 문자열 s를 줄 때, s의 뒤에 최소 몇 글자를 더 이어 써야 s를 팰린드롬(palindrome; 회문) 문자열으로 만들 수 있는지를 구하는 문제이다.

 

따라서, 문자열의 앞에서부터 각 문자(또는 두 문자)를 중심으로 하는 가장 긴 팰린드롬 문자열 길이를 구해나가다가, 마지막 문자를 포함하는 팰린드롬 문자열을 만나면 원래의 문자열 길이에서 해당 팰린드롬의 길이를 뺀 값을 출력하고 팰린드롬 탐색을 중단하면 된다.

 

문자열의 길이가 최대 40만으로 꽤 기므로, Manacher's Algorithm을 이용해 회문을 탐색하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <cmath>
#include <string>
using std::cin;
using std::cout;
using std::string;
using std::min;

string s; int len;
string str = " #";
int A[800002];
int main()
{
    cin >> len >> s;
    for (int i = 0;i < len;i++) {
        str += s[i];
        str += '#';
    }
    int center = 0, boundary = 0;
    int strlen = str.length();
    for (int i = 1;i < strlen;i++) {
        if (i > boundary) A[i] = 0;
        else A[i] = min(A[2*center - i], boundary - i);
        while ((i-A[i]-1>0) and (i+A[i]+1<strlen)) {
            if (str[i - A[i] - 1] == str[i + A[i] + 1]) A[i]++;
            else break;
        }
        if (boundary < i + A[i]) {
            boundary = i + A[i];
            center = i;
            if (boundary == strlen - 1) {
                cout << len - A[i];
                break;
            }
        }
    }
    return 0;
}