[BOJ] 1786 - 찾기 (Python)

 

 

아이디어

 

KMP 알고리즘을 이용해 문자열 T에서 P를 찾을 때마다 그 위치를 추가해 나간다.

 

 

풀이

 

첫 번째 for문에서 문자열 P에서 접두사와 접미사가 일치하는 최대 길이를 투 포인터로 찾고 리스트 lps에 저장한다.

i와 j가 가리키는 두 문자가 같으면 그 길이를 lps에 저장하고, 그렇지 않으면 lps를 참조해 비교할 문자 인덱스를 조정한다.

lps에 저장된 길이가 곧 일치하는 부분 문자열 이후의 인덱스를 나타내므로 패턴이 일치한 부분은 비교를 건너뛸 수 있다.

 

두 번째 for문에서도 같은 방법으로 문자열 T에서 문자열 P를 찾고 P를 찾으면 그 위치를 리스트 idx_list에 추가한다.

 

T = input()
P = input()
N, M = len(T), len(P)
lps = [0]*M
j = 0
for i in range(1, M):
    while j > 0 and P[i] != P[j]:
        j = lps[j-1]
    if P[i] == P[j]:
        j += 1
        lps[i] = j

j = 0
idx_list = []
for i in range(N):
    while j > 0 and T[i] != P[j]:
        j = lps[j-1]
    if T[i] == P[j]:
        if j >= M-1:
            idx_list.append(i+2-M)
            j = lps[j]
        else:
            j += 1
print(len(idx_list))
print(*idx_list)