글 읽기 - python3 메모리 초과 질문드립니다.

chsun0303 6년 전 0

주어진 단어의 길이가 50만 까지라서 이렇게 된거같은데 어떻게 해결하면 좋을지 궁금합니다.

감사합니다.

import sys

w = sys.stdin.readline().strip()
n = len(w)
suffix_arr = []
lcp_arr = ['x']

for i in range(0, n):
    suffix_arr.append([w[i:n], str(i+1)])

suffix_arr = sorted(suffix_arr)

for i in range(1, n):
    prev_suffix_len = len(suffix_arr[i - 1][0])
    count = 0

    for j in range(1, prev_suffix_len + 1):
        if suffix_arr[i - 1][0][:j] != suffix_arr[i][0][:j]:
            break
        else:
            count += 1
    lcp_arr.append(str(count))

print(" ".join([inner[1] for inner in suffix_arr]))
print(" ".join(lcp_arr))

portableangel 6년 전 1

직접 문자열을 만들지 않고 서픽스 어레이를 구성하는 O(nlogn) 또는 O(nlog^2n) 알고리즘이 존재합니다.

https://blog.naver.com/kks227/...

요 글을 참조해보세요. (제 블로그 아닙니다.)

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

문제

문제

출처

ICPC

python3 메모리 초과 질문드립니다.

chsun0303 6년 전 0

portableangel 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말