KMP 알고리즘은 문자열 탐색 알고리즘입니다. KMP는 Knuth–Morris–Pratt의 줄임말로 KMP 알고리즘을 제안한 Donald Knuth, Vaughan Pratt 그리고 James H. Morris의 이름을 따서 이름 지어졌습니다. 기본적으로 가장 간단한 문자열 탐색 알고리즘은 완전 탐색으로 찾았을 때, 문자열 M,N에 대하여 O(|M|*|N|)의 시간 복잡도를 갖게 됩니다. 하지만 KMP 알고리즘은 약간의 메모리 공간을 이용하여 불필요한 비교 연산 횟수를 줄여 시간 복잡도를 줄입니다.
예를 들어 설명하자면 samsamsung이라는 단어가 있고 samsamsong라는 단어를 찾는다면 맨 앞부터 탐색하여 u와 o에서 차이가 발생하게 됩니다. 간단한 알고리즘 같은 경우 다음 2번째 문자인 a부터 다시 탐색을 하지만 KMP같은 경우는 samsamsung의 4번째 문자 s부터 7번째 글자 s까지는 찾는 단어 samsamsong과 같다는 정보를 알고 있고, 따라서 8번째 글자인 u부터 다시 탐색합니다.
이러한 알고리즘을 구현하기 위해서는 접두사(prefix)와 접미사(suffix)의 개념을 알아야 합니다. 접두사는 앞에서부터 1~n개의 문자열, 접미사는 뒤에서부터 1~n개의 문자열입니다. 이해를 돕기 위해 다음의 예를 들겠습니다.
| samsam에서 접두사 | samsam에서 접미사 |
| s, sa, sam, sams, samsa, samsam | m, am, sam, msam, amsam, samsam |
이러한 접두사와 접미사가 같은 구간을 pi배열을 구합니다. 만약 탐색 과정 중 불일치를 발견하면 여태까지 보았던 문자열의 접미사를 찾는 문자열의 접두사로 취급하면 불필요한 비교를 안하고 그다음 문자부터 비교하면 되기 때문입니다. 이해가 잘 안되시는 분들을 위해 그림으로 추가 설명해보면, 먼저 pi 배열을 구하는 방법입니다. pi[i]는 0부터 i까지 문자열에서 접두사와 접미사가 같은 문자열일 때 일치하는 문자의 수들 중 가장 큰 값입니다.
| i | 부분 문자열 | pi[i] |
| 0 | s | 0 |
| 1 | sa | 0 |
| 2 | sam | 0 |
| 3 | sams | 1 |
| 4 | samsa | 2 |
| 5 | samsam | 3 |
이러한 pi[i]값을 구했다치고 samsabsamsam에서 samsam을 찾아봅시다.
N : 주어지는 문자열, M : 탐색하려는 문자열
| idx | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| N | s | a | m | s | a | b | s | a | m | s | a | m |
| M | s | a | m | s | a | m |
먼저, samsa까지는 M과 일치합니다. 하지만 idx=5에서 문자 불일치가 발생합니다. 우리는 samsa까지 일치했을 때 pi[4]값을 알고 있습니다. sa가 해당 문자열에서 접두사와 접미사가 일치하는 문자열이므로 뒤에 접미사 sa를 접두사로 만들어주기 위하여 match된 길이를 matched로 두고 matched - pi[matched-1]를 시작점으로 두고 (pi는 zero-base이므로 -1) matched는 pi[matched-1]로 세팅합니다. 그러면 다음과 같이 됩니다.
| idx | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| N | s | a | m | s | a | b | s | a | m | s | a | m |
| M | s | a | m |
다시 idx=5와 비교하면 문자 불일치가 발생합니다. 이 때는 pi값이 0이므로 matched=0이 되고, idx=6부터 다시 탐색합니다.
| idx | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| N | s | a | m | s | a | b | s | a | m | s | a | m |
| M | s | a | m | s | a | m |
비교결과 해당 문자열과 일치하는 것을 확인했습니다. 이 때의 시작 위치를 벡터에 넣어줍니다. 더 이상 탐색할 문자열이 존재하지 않으므로 종료합니다.
pi배열을 구하는 과정과 이를 이용하여 kmp 알고리즘을 수행하는 방법을 코드로 나타내면 다음과 같습니다.
| 입력 | 출력 |
| 첫 줄에 문자열의 길이 N이 주어집니다. 두 번째 줄에 문자열 N이 주어집니다. 세 번째 줄에 해당 문자열에서 찾으려고 하는 패턴 문자열 M의 길이가 주어집니다. 네 번째 줄에 문자열 M이 주어집니다. |
패턴 문자열이 존재하지 않을 경우{}, 존재할 경우 패턴 문자열의 시작 인덱스를 다음과 같이 출력하세요. ex) {0,3 |
| Sample Input | Sample Output |
| 12 samsabsamsam 6 samsam |
{6} |
import java.util.*;
public class Main {
static int n, m;
static String N, M;
static ArrayList<Integer> getPartialMatch(String M) {
int m = M.length();
ArrayList<Integer> pi = new ArrayList<>();
for (int i = 0; i < m; i++) {
pi.add(0);
}
int begin = 1, matched = 0;
while (begin + matched < m) {
if (M.charAt(begin + matched) == M.charAt(matched)) {
++matched;
pi.set(begin + matched - 1, Integer.valueOf(matched));
}
else {
if (matched == 0)
++begin;
else {
begin += matched - pi.get(matched - 1);
matched = pi.get(matched - 1);
}
}
}
return pi;
}
static Vector<Integer> kmpSearch(String N, String M) {
ArrayList<Integer> pi = getPartialMatch(M);
Vector<Integer> ret = new Vector<>();
int n = N.length(), m = M.length();
int begin = 0, matched = 0;
while (begin <= n - m) {
if (matched < m && N.charAt(begin + matched) == M.charAt(matched)) {
++matched;
if (matched == m) {
ret.addElement(begin);
}
}
else {
if (matched == 0) {
++begin;
} else {
begin += matched - pi.get(matched - 1);
matched = pi.get(matched - 1);
}
}
}
return ret;
}
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
N = scanner.next();
m = scanner.nextInt();
M = scanner.next();
Vector<Integer> sol = kmpSearch(N, M);
System.out.print("{");
for (int i = 0; i < sol.size() - 1; i++) {
System.out.print(String.valueOf(sol.elementAt(i)) + ",");
}
if (!sol.isEmpty()) {
System.out.print(String.valueOf(sol.lastElement()));
}
System.out.print("}");
}
}