글 읽기 - 파이썬 시간초과 문자열폭발 어디에서 시간이??

vicious1214 3년 전 0

파이썬으로 진행했습니다.

A, B 두 string을 받고 나서

kmp 구현 -> kmp로 A 안에 B가 시작하는 index 찾음 -> index 이용해서 A에서 B 제거

-> B를 제거한 A에서 또 다시 B가 나오지 않을 때까지 반복 -> 제출

로 흘러갔는데, 반복에서 시간이 초과되는 것 같은데... 구헌이 잘못된 것인지 아니면

아예 다른 방식을 취해야 하는 것인지 힌트 주시면 감사하겠습니다.

import sys

line = sys.stdin.readline().rstrip()
expl = sys.stdin.readline().rstrip()

n = len(expl)

## kmp
def getPi(pat):
    m = len(pat)
    j = 0
    pi = [0]*m

    for i in range(1, m):
        while(j > 0 and pat[i] != pat[j]):
            j = pi[j-1]
        
        if pat[i] == pat[j]:
            j += 1
            pi[i] = j

    return pi

def kmp(str, sub):
    ans = []
    pi = getPi(sub)
    n = len(str); m = len(sub); j = 0

    for i in range(n):

        while j>0 and str[i] != sub[j]:
            j = pi[j-1]

        if str[i] == sub[j]:
            if j == m-1:
                ans.append(i - m + 1)
                j = pi[j]

            else:
                j += 1
    
    return ans

## A 내에 B 위치
index = kmp(line, expl)

## B가 더이상 나오지 않을 때까지
while index != []:
    
    ## A 내에 B의 끝 index
    indpn = [(i+n) for i in index]
    
    ## B를 제외한 부분을 뽑아내기 위해
    indpn.insert(0, 0)
    index.append(len(line))
    
    temp = ""
    for i in range(len(index)):
        temp = temp + line[indpn[i]:index[i]]

    line = temp
    
    ## 다시 반복
    index = kmp(line, expl)

if line == "": line = "FRULA"
print(line)

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

문제

문제

출처

ICPC

파이썬 시간초과 문자열폭발 어디에서 시간이??

vicious1214 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말