글 읽기 - 시간 초과가 어디에서 나는 걸까요?

dreamian 6년 전 0

알고리즘은 외부 블로그나 사이트 참고하여 제대로 구현한 것 같은데 어디 부분에서 시간 초과가 나는지 모르겠습니다 ㅠㅠ

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX=5e+5+1;

char str[MAX];

vector<int> make_SA(){

    // Init
    int len=strlen(str);
    vector<int> suf(len);
    vector<int> group(len);
    vector<int> newGroup(len);
    int d;
    for(int i=0;i<len;++i){
        suf[i]=i;
        group[i]=str[i];
    }

    // Process
    for(d=1;;d*=2){
        // lamma expression
        auto cmp = [&group, d, len](int i, int j){
            if(group[i]!=group[j]) return group[i]<group[j];
            else if(i+d>=len || j+d>=len) return i>j;
            return group[i+d]<group[j+d];
        };

        // sort
        sort(suf.begin(),suf.end(),cmp);
        
        newGroup[suf[0]]=0;
        int max_v=-1;
        for(int i=1;i<len;++i){
            newGroup[suf[i]]=newGroup[suf[i-1]]+cmp(suf[i-1],suf[i]);
            max_v=max(max_v,newGroup[suf[i]]);

        }
        if(max_v==len-1) break;
        group=newGroup;
    }

    return suf;
}

vector<int> make_LCP(const vector<int> &suf){
    // Init
    int len=strlen(str);
    vector<int> lcp(len-1);
    vector<int> pos(len);
    // pos[i]는 suf의 값이 i인 접미사가 sa 배열에서 몇 번째에 위치하는지를 가리킴
    for(int i=0;i<len;++i) pos[suf[i]]=i;

    for(int i=0,k=0;i<len;++i,k=max(k-1,0)){
        if(pos[i]==len-1) continue;

        for(int j=suf[pos[i]+1];str[i+k]==str[j+k];++k);
        lcp[pos[i]]=k;
    }


    return lcp;
}

int main(){
    //freopen("sample_input.txt","r",stdin);
    scanf("%s",str);
    // Suffix Array
    auto suf=make_SA();
    for(int i=0;i<strlen(str);++i) printf("%d ",suf[i]+1);
    printf("\n");

    // LCP
    auto lcp=make_LCP(suf);
    printf("x ");
    for(int i=0;i<strlen(str)-1;++i) printf("%d ",lcp[i]);
    printf("\n");
}

djm03178 6년 전 1

strlen은 O(길이)만큼의 시간이 걸리기 때문에 79번째 줄은 O(n^2) 시간이 걸립니다.

dreamian 6년 전 0

내장 함수의 시간복잡도를 고려를 못 했네요 ㅠㅠ 답변 정말 감사합니다!

nhouyng 5년 전 0

신경좀 쓰지 그랬어요

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

문제

문제

출처

ICPC

시간 초과가 어디에서 나는 걸까요?

dreamian 6년 전 0

djm03178 6년 전 1

dreamian 6년 전 0

nhouyng 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말