[10174번] 팰린드롬

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

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

이 문제는 문자열 제한이 따로 없다. 따라서 O(n^2)으로 풀면 TLE가 날 수 있기에 O(n)알고리즘을 이용해본다.

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

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <memory.h>
 
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()
{
    int tc;
    cin >> tc;
        getchar();
    while (tc--)
    {
        tmp.clear();
        str.clear();
        memset(A, 0, sizeof(A));
        getline(cin, tmp);
 
        int len = tmp.size();
 
        for (int i = 0; i < len; i++)
        {
            str += '#';
            if ('A' <= tmp[i] && tmp[i] <= 'Z')
                tmp[i] = tmp[i] - 'A' + 'a';
            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("%s\n", ans == tmp.size() ? "Yes" : "No");
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>