[알고리즘] 문자열 검색 알고리즘 KMP 자바 구현하기 (백준 16916)
문자열 단순 비교
문자열 검색 시
주어진 문자열이
ABACAABA
주어진 패턴이
ABACAB
인 경우를 가정하자.
일반적인 방식으로 비교할 경우
| A | B | A | C | A | A | B | A |
| A | B | A | C | A | B |
문자 하나씩 비교하면 앞의 5가지 문자는 일치했지만 마지막 B가 달라서 매칭에 실패하게 되고,
| A | B | A | C | A | A | B | A |
| A | B | A | C | A | B |
한 칸 앞으로 가서 위와 같은 비교를 반복할 것이다.
눈으로 봐도 불필요한 연산이 다시 진행되는 것을 확인할 수 있다.
그러면 단순히 틀린 위치부터 탐색하면 되지 않는가?
라고 생각할 수 있지만 그렇게 비교하게 되면
3번째 위치가 A고 패턴의 시작도 A기 때문에 이 경우에 정답이 존재할 수도 있으므로 스킵하면 안된다.
그래서 접두사와 접미사를 활용하여 확실한 중복 연산들을 판별하여 줄여나가며 연산할 수 있는 KMP 알고리즘을 사용한다.
KMP 알고리즘이란?
▶ 문자열 매칭 검색 시 접두사와 접미사를 활용하여 중복 연산을 줄여나가 O(N+M) 의 속도로 빠르게 연산하는 기법
( N : 텍스트의 길이, M : 패턴의 길이 )
여기서 접두사와 접미사란
ABACAABA
란 문자열이 있을 때
접두사 : A, AB, ABA, ABAC ...
처럼 앞에서 하나씩 끊어서 본 것을 말하고
접미사 : A, BA, ABA, AABA ...
처럼 뒤에서 하나씩 끊어서 본것을 말한다.
위를 바탕으로 pi배열을 구할 수 있다.
pi배열 : 부분문자열 중에서 접두사 == 접미사 가 될 수 있는 가장 긴 것의 길이
| index | 부분문자열 | pi[index] |
| 0 | A | 0 |
| 1 | AB | 0 |
| 2 | ABA | 1 |
| 3 | ABAC | 0 |
| 4 | ABACA | 1 |
| 5 | ABACAA | 1 |
| 6 | ABACAAB | 2 |
| 7 | ABACAABA | 3 |
public static void makeTable(String pattern) {
int pLen = pattern.length();
table = new int[pLen];
int index = 0;
for(int i = 1; i < pLen; i++) {
/* index > 0 => 문자열 매칭이 시작됨
연속으로 일치하지 않으면 index 값을 돌려주어 다시 매칭 시작 */
while(index > 0 && pattern.charAt(i) != pattern.charAt(index)) {
index = table[index - 1];
}
if(pattern.charAt(i) == pattern.charAt(index)) {
index += 1;
table[i] = index;
}
}
}위 표를 자바코드로 구현하였다.
이제 위 pi배열을 활용하여
탐색을 진행해보자.
public static int search(String str, String pattern) {
int sLen = str.length();
int pLen = pattern.length();
int index = 0;
for(int i = 0; i < sLen; i++) {
while(index > 0 && str.charAt(i) != pattern.charAt(index)) {
index = table[index - 1];
}
if(str.charAt(i) == pattern.charAt(index)) {
if(index == pLen - 1) {
index = table[index];
return 1;
}
else {
index++;
}
}
}
return 0;
}문자열 : ABACAABCCCABACAABA
패턴 : ABACAABA
일 때
str[7] 에서 매칭이 실패 (C != A) 할 것이다. 그럼 지금까지 매칭이 성공했었으므로 index 값도 7이다.
실패했으니 이제 인덱스 값을 pi[6] 으로 바꿔준다.
위 표에서 확인해보면 pi[6]은 2이므로
pattern[2] 값과 str[7] 값을 비교한다. 또 실패 (C != A) 했으니
이제 인덱스 값을 pi[1] 으로 바꿔준다.
위 표에서 확인해보면 pi[1]은 0이므로
그럼 이제 다시 매칭이 다시 시작된다.
이렇게 총 문자열의 길이만큼만 반복하여 빠르게 패턴매칭이 가능해진다.
만약
문자열 : ABACAABCCCABACAABA
패턴 : ABCCAABA
이렇게 주어진다면
아까와 다르게 pi배열은 {0,0,0,0,1,1,2,1} 이고
위와 동일한 과정을 거쳐
pattern[2] 값과 str[7] 값을 비교할 때 성공 (C=C) 이므로
ABACAABCCCABACAABA
ABCCAABA
위와 같이 빨간색으로 표시한 부분의 뒤부터 계산하는 형태를 띄게 된다.
이 알고리즘을 바탕으로 백준의 부분 문자열 문제를 풀 수 있다.
문제 : https://www.acmicpc.net/problem/16916
16916번: 부분 문자열
첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다.
www.acmicpc.net
// [백준] 16916. 부분 문자열 (Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int[] table;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
String p = br.readLine();
makeTable(p);
System.out.println(search(s, p));
}
public static int search(String str, String pattern) {
int sLen = str.length();
int pLen = pattern.length();
int index = 0;
for(int i = 0; i < sLen; i++) {
while(index > 0 && str.charAt(i) != pattern.charAt(index)) {
index = table[index - 1];
}
if(str.charAt(i) == pattern.charAt(index)) {
if(index == pLen - 1) {
index = table[index];
return 1;
}
else {
index++;
}
}
}
return 0;
}
public static void makeTable(String pattern) {
int pLen = pattern.length();
table = new int[pLen];
int index = 0;
for(int i = 1; i < pLen; i++) {
/* index > 0 => 문자열 매칭이 시작됨
연속으로 일치하지 않으면 index 값을 돌려주어 다시 매칭 시작 */
while(index > 0 && pattern.charAt(i) != pattern.charAt(index)) {
index = table[index - 1];
}
if(pattern.charAt(i) == pattern.charAt(index)) {
index += 1;
table[i] = index;
}
}
}
}
