글 읽기 - KMP 알고리즘 변형 후 사용하였는데 시간초과가 납니다..

cjstjdgur123 7년 전 0

개인적으로 입력해본 결과물은 잘 출력되고, 시간복잡도도 36 + N 일 것이라 생각되는데 왜 이런지 궁금합니다..

혹은 예외 케이스가 무엇인지 알아봐주실 수 있을까요. ㅠㅠ

#include <stdio.h>
#include <string.h>

int main ( void )
{
    char check[ 1000001 ] = { 0 };
    char str[ 1000001 ], pat[ 37 ];
    scanf( "%s", str );
    scanf( "%s", pat );
    int strLen = strlen( str ), patLen = strlen( pat ), removeCnt = 0;
    
    int fail[ 37 ] = { 0 };
    for( int i = 1, j = 0; i < patLen; ++ i )
    {
        while( j > 0 && pat[ i ] != pat[ j ] ) j = pat[ j - 1 ];
        if( pat[ i ] == pat[ j ] ) fail[ i ] = ++j;
    }
    
    int history[ 1000000 ] = { 0 };
    for( int i = 0, j = 0; i < strLen; ++ i )
    {
        if( removeCnt == strLen ) break;
        while( i < strLen && check[ i ] ) i++;
        if( i >= strLen ) break;
        while( j > 0 && str[ i ] != pat[ j ] ) j = pat[ j - 1 ];
        
        
        history[ i ] = j;
        if( str[ i ] == pat[ j ] )
        {
            if( j == patLen - 1 )
            {
                // 여기서부터 문자열 n를 삭제한다.
                int chance = 0;
                for( int k = 0; k < patLen + chance; ++ k )
                {
                    if( check[ i - k ] )
                        chance++;
                    else
                        check[ i - k ] = 1, removeCnt++;
                }
                while( i > 0 && check[ i ] ) i--;
                if( check[ i ] )
                {
                    j = 0;
                }
                else
                {
                    j = history[ i ];
                    if( str[ i ] == pat[ j ] ) j++;
                }
                //printf( ">> j = %d, str[i]=%c, pat[j]=%c\n", j, str[i], pat[j] );
            }
            else
            {
                j++;
            }
        }
    }
    
    if( removeCnt == strLen )
        printf( "FRULA" );
    else
        for( int i = 0; i < strLen; ++ i )
            if( !check[ i ] )
                printf( "%c", str[ i ] );
    return 0;
}

DryType 7년 전 1

15라인과 25라인에 j = fail[j-1]이 되어야하지 않나요?

근데 그래도 시간초과가 뜨네요

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

문제

문제

출처

ICPC

KMP 알고리즘 변형 후 사용하였는데 시간초과가 납니다..

cjstjdgur123 7년 전 0

DryType 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말