[13275번] 가장 긴 팰린드롬 부분 문자열

문제 출처 :

https://www.acmicpc.net/problem/13275

알고리즘 분석 :

문제 해결에 필요한 사항

1. manacher 알고리즘 :: http://www.crocus.co.kr/1075

위의 알고리즘을 공부하고 어떻게 구현하는지 파악한다면 이 문제를 쉽게 O(n)에 해결 할 수 있다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
 
using namespace std;
 
const int MAXN = 100001 * 2;
 
string tmp, str;
 
int A[MAXN];
 
void manachers(string S, int N)
{
    int r = 0, p = 0;
    for (int i = 0; i < N; i++)
    {
        if (i <= r)
            A[i] = min(A[2 * p - i], r - i);
        else
            A[i] = 0;
 
        while (i - A[i] - 1 >= 0 && i + A[i] + 1 < N && S[i - A[i] - 1] == S[i + A[i] + 1])
            A[i]++;
 
        if (r < i + A[i])
        {
            r = i + A[i];
            p = i;
        }
    }
}
int main()
{
    cin >> tmp;
 
    int len = tmp.size();
 
    for (int i = 0; i < len; i++)
    {
        str += '#';
        str += tmp[i];
    }
    str += '#';
 
    manachers(str, str.size());
 
    len = str.size();
    int ans = -1;
    for (int i = 0; i < len; i++)
        ans = max(ans, A[i]);
 
    printf("%d", ans);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>