글 읽기 - 출력 초과가 왜 뜰까요 ㅠㅠ

zygmunt137 3년 전 0

공백이나 개행이 들어가는 것도 아닌데 출력초과가 뜨네요..

혹시 몰라서 출력할때 strip으로 공백 제거도 해봣는데..

틀렸다고 뜨면 모를까 출력초과...

text = input().strip()
pattern = input().strip()

lps = [0] * len(pattern)
cnt = [0] * len(text)


def getLps(pattern):
    global lps
    leng = 0
    i = 1
    while i < len(pattern):
        if pattern[i] == pattern[leng]:
            leng += 1
            lps[i] = leng
            i += 1
        else:
            if leng > 0:
                leng = lps[leng - 1]
            else:
                lps[i] = 0
                i += 1


getLps(pattern)

i, j = 0, 0
while i < len(text):
    if text[i] == pattern[j]:
        cnt[i] = j + 1
        i += 1
        j = (j + 1) % len(pattern)
    else:
        if j == 0:
            i += 1
        j = 0

# cnt[i] = k 일 때, i-k+1 ~ i 까지가 pattern과 매칭이 됨

i, j = 0, 0
stack = []
cntStack = []
while i < len(text):
    ch = text[i]
    if ch == pattern[j]:
        stack.append(ch)
        cntStack.append(cnt[i])
        i += 1
        j += 1
        while j == len(pattern):
            if len(stack) >= j:
                for _ in range(j):
                    stack.pop()
                    cntStack.pop()
            if len(cntStack) == 0:
                j = 0
            else:
                j = cntStack[-1]
    else:
        if j == 0:
            stack.append(ch)
            cntStack.append(cnt[i])
            i += 1
        else:
            j = lps[j - 1]

print("".join(stack).strip())

djs100201 3년 전 0

정답보다 많은 input을 출력해도 출력초과가 뜨는 경우가 있습니다.
틀렸습니다와 같다고 봐도 무방합니다.

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

문제

문제

출처

ICPC

출력 초과가 왜 뜰까요 ㅠㅠ

zygmunt137 3년 전 0

djs100201 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말