글 읽기 - 왜 시간초과가 나는지 모르겠습니다...

eltoryn7 4년 전 0

Manacher 알고리즘을 이용해서 풀었는데

어디서 시간이 초과나는지를 모르겠습니다...

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAX = 2*100001;
string S, in;
int A[MAX], result = 0;

void manacher(){
    int p = 0, r = 0, n = (unsigned)in.size();
    S+='#';
    for(int i=0; i<n; ++i){
        S+=in[i];
        S+='#';
    }
    n = (unsigned)S.size();
    for(int i=0; i<n; ++i){
        if(i > r) A[i] = 0;
        else min(r-i, A[2*p-i]);
        while(i-A[i]>0 && i+A[i]<n-1 && S[i-A[i]-1]==S[i+A[i]+1]) A[i]++;
        if(r < i+A[i]){
            p = i;
            r = i+A[i];
        }
        if(A[i]>result) result = A[i];
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> in;
    manacher();
    cout << result;
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 시간초과가 나는지 모르겠습니다...

eltoryn7 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말