NAMING 문제 시간초과

  • raccond
    raccond

    안녕하세요.
    NAMING 문제 관련하여 아래와 같이 제출을 하면 시간 초과가 발생합니다. 어떻게 해야 시간초과가 발생하지 않을까요?
    도움 부탁 드립니다.

    감사합니다. 

    #include <stdio.h>
#include <string.h>
#define MAX  500000
static char dad[MAX], mom[MAX];

main()
{
    int i,j,length,result;

    memset(dad, 0x00, sizeof(dad)); 
    memset(mom, 0x00, sizeof(mom)); 

    scanf("%s %s",&dad,&mom);
    strcat(dad,mom);
    length=strlen(dad);

    for(i=0;i<=length;i++)
    {
        result=strncmp(dad,dad+(length-i-1), i+1);
        if(result==0)
        { 
            printf("%d ",i+1);
        }
    }

}

    11년 전
2개의 댓글이 있습니다.
  • Kureyo
    Kureyo

    strncmp는 O(n)의 시간복잡도를 가진 구현이며, 50만의 제곱은 굉장히 오래걸립니다. 알고리즘 자체가 달라져야합니다.. KMP나 Suffix Array에 대해 공부해보세요


    11년 전 link
  • raccond
    raccond

    감사합니다!!!


    11년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.