[BOJ] 1305 - 광고 (Python)

 

 

아이디어

 

문자열의 접두사와 접미사가 일치하는 최대 길이를 구한다.

 

 

풀이 #1

 

KMP 알고리즘을 이용하여 부분 일치 테이블 lps를 구한 후, 맨 마지막 문자의 부분 일치 값을 전체 길이 N에서 뺀다. 

 

def last_lps():
    S = input()
    lps = [0]*L
    j = 0
    for i in range(1, L):
        while j > 0 and S[i] != S[j]:
            j = lps[j-1]
        if S[i] == S[j]:
            j += 1
            lps[i] = j
    return lps[-1]

L = int(input())
print(L-last_lps())

 

 

테이블 생성 코드를 함수로 따로 빼지 않은 코드는 메모리 사용량은 비슷했으나 더 느렸다.

# 더 느린 코드
L = int(input())
S = input()
lps = [0]*L
j = 0
for i in range(1, L):
    while j > 0 and S[i] != S[j]:
        j = lps[j-1]
    if S[i] == S[j]:
        j += 1
        lps[i] = j
print(L-lps[-1])

 

 

 

풀이 #2

 

다른 분의 풀이를 보니 부분 일치 테이블에 모든 부분 문자열에 대해 저장할 필요가 없다는 것을 깨달았다.

문자가 일치하지 않을 때에만 그 직전 인덱스에 일치했던 길이를 저장하여 부분 일치 테이블 lps를 만든다.

 

def last_lps():
    lps = [0]*L
    i = 1
    j = 0
    while i < L:
        if S[i] == S[j]:
            j += 1
        elif j > 0:
            lps[i-1] = j
            j = lps[j-1]
            continue
        i += 1
    return j

L = int(input())
S = input()
print(L-last_lps())