글 읽기 - KMP 어디가 틀린 걸까요

ebbunnim 3년 전 0

입력케이스, 반례 다 해봤는데

왜 채점시 처음부터 틀렸다고 할까요?

def getpi(): 
    j = 0
    for i in range(1,L): 
        while j > 0 and patterns[i]!=patterns[j]:
            j = PI[j-1] 

        if patterns[i] == patterns[j]:
            j += 1
            PI[i] = j
    return

if __name__ == '__main__':
    patterns = list(input())
    L = len(patterns)
    PI = [0]*L
    getpi()
    print(max(PI))

shg9411 3년 전 4

반례입니다.

input : baaa

output : 0

answer : 2(aa)

ebbunnim 3년 전 2

접두사랑 접미사를 비교할 때 접두사의 시작점을 항상 인덱스0으로 설정했었네요.

아래처럼 메인 함수를 바꿔서 맞았습니다!

shg9411님 감사합니다.

if __name__ == '__main__':
    patterns = list(input())
    L = len(patterns)
    res =0
    for a in range(L): # baaa의 경우와 같이 접두사를 인덱스 0 으로 고정하지 않고, baaa -> aaa -> aa 이렇게 변경해 나가야 함
        sub_patterns = patterns[a:]
        PI = [0]*len(sub_patterns)
        getpi(sub_patterns)
        if res < max(PI):
            res = max(PI)
    print(res)

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

문제

문제

출처

ICPC

KMP 어디가 틀린 걸까요

ebbunnim 3년 전 0

shg9411 3년 전 4

ebbunnim 3년 전 2

shg9411님 감사합니다.

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말