[BOJ] 13506 - 카멜레온 부분 문자열 (Python)

 

 

아이디어

 

문자열의 접두사와 접미사가 일치하면서 문자열 중간에 등장하는 가장 긴 부분 문자열을 찾는다.

 

 

풀이

 

문자열 S에 대한 부분 일치 테이블 lps를 만든다.

S의 접두사와 접미사가 일치하면서 가장 긴 부분 문자열 S[-j:]가 문자열 S의 중간에 등장하면 S[-j:]를 출력한다.

S의 중간에 등장하지 않으면 그 다음 길이의 부분 일치 문자열을 찾아 출력하고, 없으면 -1을 출력한다.

 

lps[-1]이 0이면 슬라이싱이 S[-0:]로 되어 문자열 S를 나타내고, S는 S[1:-1]에 포함되지 않아 if문이 실행되지 않는다.

또 lps[-1]-1은 -1이 되어 lps[-1]을 가리키게 되므로 elif문도 실행하지 않고 else문의 -1을 출력한다.

 

def solution():
    S = input()
    N = len(S)
    lps = [0]*N
    j = 0
    for i in range(1, N):
        while j > 0 and S[i] != S[j]:
            j = lps[j-1]
        if S[i] == S[j]:
            j += 1
            lps[i] = j
    if S[-j:] in S[1:-1]:
        print(S[-j:])
    elif lps[j-1]:
        print(S[-lps[j-1]:])
    else:
        print(-1)

solution()