kmp 알고리즘에 대한 간단한 개인 정리
kmp 알고리즘을 하루동안 고민한 알고리즘이었던 만큼 정리하고자 작성하게 되었습니다.
kmp 알고리즘을 처음 들으면 접두사와 접미사의 사용 이유부터 인덱싱 접근 방식 그리고 문자열(text)와 패턴문자열(pattern)을 이해하기 어려웠습니다.
크게 앞서 언급한 이 2가지를 제대로 이해해야 문자열 파싱을 제대로 이해할 수 있습니다.
⚠️ 여기서 text란 문제에서 주어지는 큰 문자열이고, 패턴 문자열이란 text에서 서칭하는데 쓰이는 작은 문자열을 뜻합니다.
1.접두사 & 접미사
kmp 알고리즘에서는 접두사와 접미사를 체크하는 방식으로 패턴으로 간주할 문자열의 특징들을 1차로 뽑아냅니다. 밑에서 설명하는 저장리스트는 실제로 문자열의 접두사와 접미사가 얼마나 일치하는지 저장하는 리스트입니다. 접두사와 접미사에 대한 특징을 추출하는 이유는 패턴 문자열에 대한 정보를 추출하여 이를 활용하기 위해서입니다.
개인적으로 이 부분에 대한 유튜브 강의로 어려웠던 부분을 이해하는데 1분도 안 걸려서 소개합니다. (맨 하단 링크)
패턴 문자열에서 특징 추출하는 방법
1. 문자열을 서칭하는데 인덱스를 가리키는 2개의 변수(i,j)를 할당해줍니다. -> i= back_searching index, j= front_searching_index라고 표현 2. 만약 패턴 문자열이 1이 아니면 3번부터 진행합니다. 2-1. 만약 패턴 문자열이 1이면 해당 문자열 자체가 패턴이 됩니다. 3. i = 1 , j =0 으로 두고 시작합니다. 4. 만약 i번째 문자와 j번째 문자가 같다면 j값을 i번째 저장리스트에 저장하고 i+=1, j+=1 5. 만약 다르다면, 5-1번 과 5-2번 중 상황에 맞는 과정을 한번 진행합니다. 5-1. 만약 j가 0이 아니라면 문자열의 앞부분 방향으로 더 찾아보기 위해 j값에 저장리스트 j-1번쨰 값을 넣어줍니다. 5-2. 만약 j가 0이라면 기존에 찾았던 앞부분 문자열은 다 찾았기에 i에 1을 더해 뒤로 더 탐색합니다. 6. 4번부터 5번까지 i가 문자열 끝까지 올때까지 계속 진행합니다.
2. text와 pattern을 비교하는 방법
실제로 긴 문자열에서 pattern이 몇 번 나타나는지 확인하는 알고리즘이기에 긴 문자열 내에서 탐색하며 개수를 찾습니다. 이때, 접두사와 접미사의 정보를 활용하여 빠르게 탐색합니다.
실제로 text = 'ababacabacaabacaaba' 이고 pattern = 'abacaaba' 인 경우, 2 문자열은 3번째 index에서 불일치임을 확인합니다. 이때 접두사와 접미사를 체크한 리스트에서 3번째 index에서부터 다시 비교하고자 인덱스를 다시 불러오고, 그 이외의 과정은 1번과 마찬가지로 긴 문자열의 index와 pattern 문자열의 인덱스를 옮기면서 탐색합니다.
import sys
# text = 'ababacabacaabacaaba'
# str_example = 'abacaaba'
text = sys.stdin.readline()[:-1]
str_example = sys.stdin.readline()[:-1]
lst = [0 for _ in range(len(str_example))]
def find_pre_sub(val_string):
i = 1
j = 0
if i == len(val_string): # 길이가 1인걸 예외처리했습니다.
if val_string[j] == val_string[i-1]:
j+=1
lst[i-1] = j
i+=1
while i < len(val_string):
# print(i, lst)
if val_string[j] == val_string[i]:
j +=1
lst[i] = j
i +=1
else:
if j != 0:
j = lst[j-1]
else:
i +=1
find_pre_sub(str_example)
# print(lst)
def kmp(text, pattern):
cnt = 0
result_lst = []
i = 0
j = 0
if i == len(text)-1: # 길이가 1인 경우를 예외처리했습니다.
if pattern[j] == text[i-1]:
result_lst.append(i-j+1)
j+=1
i+=1
cnt+=1
while i < len(pattern):
# print(j,i)
if text[j] == pattern[i]:
if j == len(text)-1:
result_lst.append(i-j+1)
# print("matched",j,i)
cnt += 1
j = lst[j-1]
# print(j,i)
else:
i+=1
j+=1
elif text[j] != pattern[i]:
# print("not matching")
# time.sleep(1)
if j != 0:
j = lst[j-1]
else:
i+=1
#print(j, i)
return cnt ,result_lst
cnt, total = kmp(str_example, text)
print(cnt)
for i in range(cnt):
print(total[i], end=' ')
print()
