KMP 알고리즘은 대표적인 문자열(String) 매칭 알고리즘입니다.
문자열 알고리즘은 문자열이 있을 때 그 문자열에 포함된 특정 문자열을 찾는 데 사용됩니다. (패턴 매칭)
문자열 패턴 매칭 알고리즘은 대표적으로 4가지가 있습니다.
1. 단순 완전 탐색 알고리즘
2. 카프-라빈 알고리즘
3. KMP 알고리즘
4. 보이어-무어 알고리즘
단순하게 모든 경우를 다 비교해서 특정 문자열을 찾을 수 있지만, 시간이 오래 걸리는 문제점이 있습니다.
반면, KMP 알고리즘은 접두사와 접미사 개념을 활용하여 특정 문자열 탐색 시간을 감소시킬 수 있습니다.
KMP 시간 복잡도
KMP 알고리즘 시간 복잡도 : O(N+M)
N : 문자열 길이
M : 탐색하려는 패턴의 길이
접두사(prefix) 접미사(suffix)란?
abcdefgabc
접두사 : abcde (문자열의 앞에서 부터)
접미사 : gabc (문자열의 뒤에서 부터)
1. (접두사==접미사) 배열 생성
문자열: abcdefgabc
위 표는 각 부분 문자열에 대해 접두사와 접미사가 일치하는 경우의 길이를 나타낸 것 입니다.
이렇게 나타낸 이유는 접두사와 접미사가 일치하는 경우에 점프(jump)를 수행할 수 있기 때문입니다. (일치하지 않는 경우가 발생하면 일치했던 부분까지 되돌아가서 다시 검사를 할 수 있습니다.)
위 배열을 생성하는 알고리즘 ( = 부분 일치 테이블 생성)
[초기 상태 ]
| a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|
| i | j | ||||||
| 0 |
[시작]
| a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|
| i | j | ||||||
| 0 | 0 |
문자 i와 j가 가리키는 문자가 다르기 때문에 j 1 증가
| a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|
| i | j | ||||||
| 0 | 0 | 1 |
문자 i와 j가 가리키는 문자가 같기 때문에 i, j 모두 1 증가
i의 인덱스(0) + 1= 1 저장
| a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|
| i | j | ||||||
| 0 | 0 | 1 |
| a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|
| i | j | ||||||
| 0 | 0 | 1 | 0 |
다시 i 와 j를 비교해서 다르면 “i는 i-1의 값 = 0” 인 인덱스 0으로 이동
다르기 때문에 0 저장 , j 1 증가
| a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|
| i | j | ||||||
| 0 | 0 | 1 | 0 |
i와 j를 비교
같기 때문에 i, j 모두 1 증가 (a == a)
| a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|
| i | j | ||||||
| 0 | 0 | 1 | 0 |
다시 비교 (b ≠ a) 다르기 때문에 다시 “i는 i-1의 값 = 0” 인 인덱스 0으로 이동
| a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|
| i | j | ||||||
| 0 | 0 | 1 | 0 | 1 |
같기 때문에 i, j모두 1증가 (a==a)
i의 인덱스(0) + 1= 1 저장.
| a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|
| i | j | ||||||
| 0 | 0 | 1 | 0 | 1 | 1 |
| a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|
| i | j | ||||||
| 0 | 0 | 1 | 0 | 1 | 1 | 2 |
같기 때문에 i, j모두 1 증가 (b==b)
i의 인덱스(1) = 2 저장.
| a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|
| i | j | ||||||
| 0 | 0 | 1 | 0 | 1 | 1 | 2 | 3 |
(a==a)
i의 인덱스(2) + 1= 3 저장.
public class Main {
static int patternSize;
static String pattern; // abacaaba
static int[] patternTable;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
pattern = br.readLine();
patternSize = pattern.length();
patternTable = new int[patternSize];
int i=0;
for(int j=1; j<patternSize; j++) {
while(i>0 && pattern.charAt(i) != pattern.charAt(j)) { // index범위를 넘어서지 않고 && 문자가 다르다면
i = patternTable[i-1];
}
if(pattern.charAt(i) == pattern.charAt(j)) { // 문자가 같다면
i += 1;
patternTable[j] = i;
}
}
System.out.println(Arrays.toString(patternTable));
}
}매칭
위에서 생성한 부분 일치 테이블을 사용하여 문자열 매칭을 수행합니다.
| i | 부분 문자열 | 최대 일치 길이 |
|---|---|---|
| 0 | a | 0 |
| 1 | ab | 0 |
| 2 | aba | 1 |
| 3 | abac | 0 |
| 4 | abaca | 1 |
| 5 | abacaa | 1 |
| 6 | abacaab | 2 |
| 7 | abacaaba | 3 |
예시
문자열 : ababacabacaabacaaba
찾을 문자열 : abacaaba
| i | a | b | a | b | a | c | a | b | a | c | a | a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| j | a | b | a | c | a | a | b | a | |||||||||||
| 0 | 0 | 1 | 0 | 1 | 1 | 2 | 3 |
- 다른 문자가 나타날 때까지 계속 비교를 진행합니다.
- b, c가 서로 다르기 때문에 점프를 수행합니다.
이때 b, c가 다르기 때문에 찾으려는 문자열의 c 인덱스에서 1을 뺀 a의 부분 일치 테이블의 값이 1입니다.
이 뜻은 찾으려는 문자열의 1번 인덱스까지는 일치했다는 의미입니다.
| i | a | b | a | b | a | c | a | b | a | c | a | a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| j | a | b | a | c | a | a | b | a | |||||||||||
| 0 | 0 | 1 | 0 | 1 | 1 | 2 | 3 |
- 점프한 상태는 j=1(b) / i=3(b)인 상태입니다.
찾으려는 문자열의 1번 인덱스까지는 일치를 했기 때문에 2번 인덱스부터 문자열과 비교를 시작합니다.
| i | a | b | a | b | a | c | a | b | a | c | a | a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| j | a | b | a | c | a | a | b | a | |||||||||||
| 0 | 0 | 1 | 0 | 1 | 1 | 2 | 3 |
- b와 a가 다르기 때문에 점프를 수행합니다.
찾으려는 문자열의 b 직전 a의 부분 일치 테이블의 값이 1입니다.
따라서 점프는 찾으려는 문자열의 1번 인덱스까지는 일치했다는 의미가 됩니다. - 점프를 수행하면 상태는 j=1(b) / i=7(b)인 상태입니다.
다시 비교를 시작합니다.
| i | a | b | a | b | a | c | a | b | a | c | a | a | b | a | c | a | a | b | a |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| j | a | b | a | c | a | a | b | a | |||||||||||
| 0 | 0 | 1 | 0 | 1 | 1 | 2 | 3 |
- 일치하는 부분 문자열을 찾았습니다.
그러나, 계속 진행하면 한 번 더 일치하는 부분 문자열을 찾을 수 있습니다. - 예를 들어 위 상황은 부분 문자열을 찾은 상황입니다.
찾으려는 문자열의 마지막 값 a의 부분 일치 테이블에서 값은 3입니다.
이 뜻은 접두어와 접미어가 일치하는 길이가 3개이기 때문에 찾으려는 문자열의 3번 인덱스부터 다시 비교를 시작하면 됩니다.
import java.io.*;
import java.util.*;
public class Main {
static String string; // 문자열 :ababacabacaabacaaba
static int stringSize;
static int patternSize;
static String pattern; // 찾을 문자열 : abacaaba
static int[] patternTable; // [0, 0, 1, 0, 1, 1, 2, 3]
static int[] kmpTable;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
string = br.readLine();
stringSize = string.length();
pattern = br.readLine();
patternSize = pattern.length();
patternTable = new int[patternSize];
int i=0;
for(int j=1; j<patternSize; j++) {
while(i>0 && pattern.charAt(i) != pattern.charAt(j)) { // index범위를 넘어서지 않고 && 문자가 다르다면
i = patternTable[i-1];
}
if(pattern.charAt(i) == pattern.charAt(j)) { // 문자가 같다면
i += 1;
patternTable[j] = i;
}
}
KMP();
}
static void KMP() {
kmpTable = new int[patternSize];
int j=0;
for(int i=0; i<stringSize; i++) {
while(j>0 && string.charAt(i) != pattern.charAt(j)) { // 다른 경우
j = patternTable[j-1];
}
if(pattern.charAt(j) == string.charAt(i)) {
if(j == patternSize-1) { // 찾으려는 문자열의 끝까지 도달했다면 -> 일치하는 문자열을 찾은 것 이다.
System.out.println((i-patternSize+2)+"번에서 일치하는 문자열 발견");
j = patternTable[j];
}
else { // 계속 매칭
j++;
}
}
}
}
}[백준] 찾기 (1786) 문제를 풀어보시는걸 추천해 드립니다.
