KMP 알고리즘
- 패턴 매칭 알고리즘의 하나로, 주어진 문자열에서 패턴과 일치하는 부분 문자열이 있는지 찾는 알고리즘
- 일반적인 반복문을 통한 해결방법은 O(N^M)의 시간복잡도를 가지지만, 해당 알고리즘은 O(N+M)의 시간복잡도로 매우 효율적이다.
- 패턴에서 접두사와 접미사를 이용해 중복된 검색을 줄이는 방식임
동작 원리
1. 패턴 문자열에서 0부터 i번째 문자열로 잘랐을 때 접미사와 접두사가 같은 최대 길이를 기록한 배열(LPS)을 생성한다.
2. 텍스트에서 패턴을 비교하고, 검색 중 불일치가 발생하면 LPS배열을 참고해 패턴의 다음 탐색 시작 위치를 결정한다.
예시
- 텍스트: "ABC ABCDAB ABCDABCDABDE"
- 패턴: "ABCDABD"
1. LPS (부분 일치 테이블) 생성
0부터 i번째 문자열로 잘랐을 때 접미사와 접두사가 같은 최대 길이를 기록한 배열(LPS)을 생성한다.
| 문자 | A | B | C | D | A | B | D |
| 인덱스 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| LPS 값 | 0 | 0 | 0 | 0 | 1 | 2 | 0 |
2. 문자열 검색 시작
텍스트와 패턴이 일치하지 않을 경우, LPS 테이블을 사용하여 패턴 내에서 최대한 불필요한 재비교를 피함
1) 처음 비교 시작 (i = 0, j = 0)
텍스트의 첫 번째 문자 A와 패턴의 첫 번째 문자 A를 비교
- 텍스트: "ABC ABCDAB ABCDABCDABDE"
- 패턴: "ABCDABD"
두 문자가 일치하므로 i와 j를 각각 1씩 증가시킵니다.
2) 다음 문자 비교 (i = 1, j = 1)
다음으로 텍스트의 두 번째 문자 B와 패턴의 두 번째 문자 B를 비교
- 텍스트: "ABC ABCDAB ABCDABCDABDE"
- 패턴: "ABCDABD"
일치하므로 i와 j를 다시 1씩 증가
3) 계속되는 비교 (i = 2, j = 2)
텍스트의 세 번째 문자 C와 패턴의 세 번째 문자 C도 일치
- 텍스트: "ABC ABCDAB ABCDABCDABDE"
- 패턴: "ABCDABD"
일치하므로 i = 3 및 j = 3으로 이동
4) 불일치 발생 (i = 3, j = 3)
네 번째 문자에서 텍스트의 문자 (공백)과 패턴의 문자 D가 일치하지 않음
- 텍스트: "ABC ** **ABCDAB ABCDABCDABDE"
- 패턴: "ABCDABD"
불일치 시, LPS 테이블을 참고하여 패턴의 어느 위치로 돌아갈지 결정함. 현재 j = 3이고, LPS 테이블에서 LPS[3] = 0이므로, 패턴의 시작 부분으로 돌아야 함(j = 0). 하지만 텍스트에서 이미 비교한 문자는 건너뛰지 않고 계속 비교하므로 i는 4로 증가
5) 패턴 계속 비교 (i = 4, j = 0)
패턴을 다시 처음부터 시작하면서, 텍스트의 4번째 문자 A와 패턴의 첫 번째 문자 A를 비교
- 텍스트: "ABC ABCDAB ABCDABCDABDE"
- 패턴: "ABCDABD"
문자가 일치하므로 i = 5 및 j = 1로 이동
6) 패턴 계속 비교 (i = 5 ~ 7, j = 1 ~ 3)
텍스트의 문자 B, C, D와 패턴의 문자 B, C, D가 차례로 일치
- 텍스트: "ABC ABCDAB ABCDABCDABDE"
- 패턴: "ABCDABD"
- 텍스트: "ABC ABCDAB ABCDABCDABDE"
- 패턴: "ABCDABD"
- 텍스트: "ABC ABCDAB ABCDABCDABDE"
- 패턴: "ABCDABD"
i = 8 및 j = 4로 이동
7) 다시 불일치 발생 (i = 8, j = 4)
여기서 텍스트의 문자 A와 패턴의 문자 A가 일치
- 텍스트: "ABC ABCDAB ABCDABCDABDE"
- 패턴: "ABCDABD"
다시 일치하므로 i = 9 및 j = 5로 이동
8) 최종 불일치 (i = 10, j = 6)
그러나 그다음 문자에서 텍스트의 문자 B와 패턴의 문자 B가 일치
- 텍스트: "ABC ABCDABB ABCDABCDABDE"
- 패턴: "ABCDABBD"
마지막으로 D가 일치
장점
- 시간 복잡도를 효과적으로 줄일 수 있음
단점
- 과정이 복잡해 이해하기 어려움
- 초기 LPS 배열을 만드는 단계가 있어 패턴 크기가 작으면 오히려 비효율적일 수 있음
코드 구현
DP를 이용한 코드
>> 이전 항의 값을 별도 배열에 저장!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class KMP알고리즘 {
static char[] text;
static char[] pattern;
static int[] pi;
static int max;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
text = br.readLine().toCharArray();
pattern = br.readLine().toCharArray();
KMP();
}
private static void KMP() {
getPi();
int len = text.length;
int j = 0;
max = 0;
for (int i=0; i<len; i++) {
while (j>0 && text[i] != pattern[j]) {
if (max < j) {
max = j;
}
j = pi[j-1];
}
if (text[i] == pattern[j]) {
// j 패턴 끝까지 도달했으면 종료
if (j == pattern.length-1) {
System.out.println(pattern.length);
return;
} else {
j++;
}
}
}
System.out.println(max);
}
// 패턴 문자배열을 0부터 i번 인덱스까지 잘랐을 때
// 접두사와 접미사가 같은 최대 개수를 담은 배열을 생성하는 메서드
private static void getPi() {
int len = pattern.length;
pi = new int[len];
int j=0;
for (int i=1; i<len; i++) {
// i위치와 j위치 값이 다를 때
while (j>0 && pattern[i] != pattern[j]) {
j=pi[j-1];
}
// 같을 때
if (pattern[i] == pattern[j]) {
pi[i] = ++j;
}
}
}
}