[알고리즘] KMP 문자열 매칭 알고리즘
길이가 100’000 인 문자열에서 길이가 10 인 특정 문자열을 찾으려면 어떻게 해야 할까요?
이번 포스트에서는 문자열 탐색을 위한 알고리즘은 무엇이 있는지 알아보겠습니다.
하나씩 전부 비교하기 O(M x N)
구현이 가장 간단한 방법은 찾는 문자열을 100’000 자에서 한 글자씩 이동하면서
전부 비교하는 방법 입니다.
100’000 자를 한 개씩 꺼내 길이가 10인 문자열을 찾는 구현이므로 시간 복잡도는
O(100’000 x 10) 즉, O(M x N) 입니다.
이 알고리즘은 구현은 간단하지만 시간 복잡도에서 그만큼 손해를 본다는 단점이 있습니다.
KMP 알고리즘 O(M + N)
KMP 알고리즘은 접두사, 접미사의 길이를 이용하여 탐색 중 건너뛰기가 가능한 알고리즘 입니다.
여기서 접두사와 접미사를 확인하는 대상은 찾고자 하는 문자열입니다.
문자열의 원본을 M, 찾고자 하는 문자열을 N 이라고 지칭하겠습니다.
먼저, 문자열 N에서 접두사와 접미사를 확인해 반복되는 문자열이 존재하는지 확인합니다.
문자열 N에 저장된 각 문자를 value, 각 위치에 해당하는 인덱스를 String Index
접두사, 접미사를 확인하면서 기록하는 값을 KMP Index라고 하겠습니다.
KMP Index 를 작성하는 방법은 현재 위치(String Index)까지 문자열에서 접두사와 접미사가 같은지
확인하고 같다면 같은 접미사 인덱스(String Index)의 다음 인덱스(String Index)를
KMP Index에 저장합니다.
접미사에 새로운 문자가 나와서 접두사와 다를 경우 KMP Index 에는 0을 저장합니다.
KMP Index 가 완성되면 문자열 M과 비ㅣ교를 시작합니다.
문자열 M과 N을 비교하면서 다른 문자열이 나왔을 때 까지 진행합니다.
문자열 M과 N을 비교하는 중 다른 문자가 나올 경우, 다른 문자열이 나온 위치에서
(위 그림에서는 빨간색 문자입니다.)
바로 이전 위치에 저장되어 있는 KMP Index 위치로 이동해서 다시 비교합니다.
이번 비교에서 문자가 같을 경우 문자열 N을 이동시켜서 문자열 M과 다시 비교합니다.
문자가 다를 경우는 다시 문자열 N의 이전 위치로 이동하여 KMP Index를 확인하는 과정을 반복합니다.
정리하면
- 접두사와 접미사를 확인해 KMP Index 생성
- 문자열 M과 문자열 N을 비교
- 비교 중 다른 문자가 나올 경우, 직전 문자에 해당하는 KMP Index 확인
- 문자열 N에서 KPM Index 위치에 해당하는 위치부터 다시 문자열 M과 비교
- 문자열이 다른 경우 위 과정을 반복
- KMP Index로 전부 비교했지만 완전히 다를 경우, 문자열 N을 한 칸 이동시킵니다.