KMP(Knuth-Morris-Pratt) 알고리즘은 두 문자열 s1과 s2가 주어지고, s1가 s2보다 길 때, s1 안에 s2가 포함되어 있는지를 탐색하는 알고리즘입니다.
1. 필요성
가장 기초적으로 브루트 포스를 이용해 s1에 s2가 포함되는 지를 확인하기 위해서는 아래와 같은 단계를 거쳐야 합니다.
2중 반복문을 통해 한 칸씩 옆으로 이동하며 비교를 해야 하기 때문에 시간 복잡도는 O(s1.length * s2.length)가 나오게 됩니다. 이를 개선하기 위해 등장한 알고리즘이 바로 KMP 알고리즘입니다.
위의 사진에서 첫 비교 부분만 분리해서 가져와 보겠습니다.
이미 앞에 세 자리는 같다는 것을 확인했고, 네 번째 자리에서 불일치가 발생했습니다. 그렇다면 '앞에서 이미 연산을 한 세 자리 정보를 사용할 수는 없을까?' 생각해 볼 수 있습니다.
2. 실패 함수
위에서 생각한 아이디어를 실패 함수(Failure Function)라는 개념을 이용해 구현할 수 있습니다. 실패 함수란, 문자열 일치 여부를 검사하다가, 불일치가 발생하면 (일치에 실패하면) 어떤 조치를 취해야 하는지에 대한 함수입니다.
기본적인 아이디어는 이렇습니다. '문자열 s2에 반복되는 부분이 존재한다면, 해당 부분은 다시 검사할 필요가 없지 않을까?'. 위의 예시에서 s2는 abab로 ab가 두 번 반복되는 형태입니다. 그렇다면, 굳이 한 칸씩 옮기며 검사를 하는 것이 아니라, 반복되는 부분은 검사를 할 필요가 없기 때문에 과감하게 스킵을 해 주는 것입니다.
실패 함수에서는 i 번째 칸에서 불일치가 발생했다면, s2를 몇 칸 이동시켜주어야 하는지에 대한 값을 특정 배열에 저장시켜줍니다. 이 배열을 fail 배열이라고 하겠습니다. 그리고 s2가 앞 뒤로 몇 개의 문자가 반복되는 형태인가에 대한 정보를 이용해 fail 배열을 채워나갑니다.
요약하자면, 실패 함수란 s1과 s2를 비교하기 이전에, s2만을 가지고 s2에 대한 fail 배열을 만들어주는 함수이며, 이 fail 배열은 s2의 i 번째 문자에서 불일치가 발생했을 때 s2를 얼마나 이동시켜서 다시 s1과 비교를 해야 하는가를 알려주는 배열입니다.
3. 실패 함수의 구현
이제 fail 배열을 생성하는 과정을 알아보겠습니다. 우선 s2를 abcabcacab라고 하겠습니다.
우선 처음에 a만 확인합니다. a는 반복되는 형태가 없으니 fail[0]에 0을 저장합니다. 다음으로 ab를 확인합니다. 여기서도 반복되는 형태가 없으니 fail[1]에 0을 넣어줍니다. 그다음 abc를 확인합니다. 여기도 반복되는 형태가 없으니 fail[2]도 0입니다.
다음으로 abca를 확인합니다. abca는 양 끝에 a가 반복되는 형태입니다. 문자 하나가 반복되기 때문에 fail[3]에는 1을 넣어줍니다.
이런 식으로 abcab는 문자 두 개가 반복되기 때문에 fail[4]는 2, abcabc는 문자 세 개가 반복되기 때문에 fail[5]는 3을 넣어줍니다.
그리고 abcabca를 보겠습니다. abcabca는 아래의 그림처럼 abca가 두 번 반복되는 형태입니다.
abcabcac는 반복되는 형태가 없고, abcabcaca는 다시 양 끝에 a만 반복되는 형태입니다.
이런 식으로 마지막까지 채워 넣으면 다음과 같은 fail 배열을 얻을 수 있습니다.
구현에 따라 반복되는 형태가 없을 경우를 0 대신 -1로 하여 fail 배열을 채워 넣는 경우도 있습니다. 이 경우에는 제가 만든 예시에 모두 -1을 하여 생각하시면 됩니다.
이 과정을 코드로 구현하기 위해 s2를 자기 자신과 비교하는 방법을 사용합니다. 우선 fail[0]은 'a' 1자리 글자밖에 없기 때문에 0으로 초기화해줍니다. 시작은 비교 대상을 한 칸 옮겨둔 상태로 비교를 시작합니다.
이때 두 개의 int형 변수를 사용하는데, begin과 m입니다.
begin은 비교가 되는 대상, 즉 위의 그림에서 아래쪽 배열의 시작 위치를 알려주기 위한 변수이고, m은 begin으로부터 몇 번째 칸을 검사할 지에 대한 변수입니다.
위의 그림에서 b와 a를 처음에 비교하겠죠? 이는 s2[begin+m]과 s2[m]을 비교함으로써 구현할 수 있습니다. 처음에 begin은 1, m은 0입니다. 아래쪽의 비교 대상 s2가 1에서 시작하고, s2[begin+m]인 b와 s2[m]인 a를 검사하고 있다는 뜻입니다.
그리고 다음의 단계를 따라가며 작동합니다.
1. 만약 s2[begin+m]와 s2[m]가 같다면? m에 1을 더해준다. 그리고 fail배열에 m을 써준다.
--> begin으로부터 m번째 글자까지 반복된다는 뜻이므로.
2. s2[begin+m]와 s2[m]가 다르다면(불일치가 발생한다면)? m이 0이면 begin에 1을 더해줌으로써 아래쪽 배열을 오른쪽으로 한 칸 이동시켜준다. 만일 m이 0이 아니라면, 이미 일치하는 부분이 앞에 있었다는 뜻이므로 begin에는 m-fail[m-1]만큼 더해주고, m에는 fail[m-1]을 넣어준다.
--> 이 말의 뜻은 위에서 KMP의 개념을 설명하며 언급한 내용인데, 이미 반복되는 부분이 앞에 존재하므로, 해당 부분을 스킵하고 오른쪽으로 이동시켜준다는 뜻입니다.
아래의 그림을 보면 이해에 도움이 될 것 같습니다.
이 과정을 문자열 끝까지 반복해줍니다.
JAVA를 이용한 코드로 구현하면 다음과 같습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public static void failure(){
int m = 0; // m은 0으로 초기화
int begin = 1; // begin은 1로 초기화
while(begin+m < s2.length()){ // s2의 끝까지 검사한다.
if(s2.charAt(begin+m) == s2.charAt(m)){ // 일치하면 m을 1 증가시키고 fail 배열에 값을 추가해준다.
m++;
fail[begin+m-1] = m;
}
else{ // 일치하지 않으면, 아래쪽 배열을 옮겨준다.
if(m == 0) {
begin++;
}
else {
begin += m-fail[m-1];
m = fail[m-1];
}
}
}
}
|
cs |
3. KMP의 구현
KMP의 구현도 사실 위에서 구현한 실패 함수와 크게 다르지 않습니다. 실패 함수를 구현할 때 사용한 알고리즘이 KMP를 구현할 때 똑같이 사용되기 때문입니다. 따라서 자세한 설명은 생략하도록 하겠습니다.
실패 함수를 구할 때는 s2를 자기 자신과 비교했지만, KMP에서는 s1과 s2를 비교하는 것뿐입니다. 그리고 fail 배열을 작성하는 코드 대신, s1에서 s2와 일치하는 부분을 발견했을 때, 이를 알려주는 코드를 삽입해주면 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public static void kmp(){
int m = 0; // m = 0으로 초기화
int begin = 0; // 실패 함수와 다르게 KMP에서는 두 문자열 모두 처음부터 비교를 시작
while(begin+m < s1.length()){
if(s1.charAt(m) == s2.charAt(m)){ // 두 문자가 같으면, m을 1 증가
m++;
if(m >= s2.length()){ // m이 s2의 길이와 같다는 말은, s1에서 s2를 발견했다는 뜻
System.out.println("Find!");
System.exit(0);
}
}
else { // 두 문자가 다르면, fail 배열을 확인해서 s2를 우측으로 이동
if (m == 0) {
begin++;
} else {
begin += m - fail[m - 1];
m = fail[m - 1];
}
}
}
}
|
cs |
이렇게 KMP를 사용하면 시간 복잡도가 O(s1.length) 정도로 줄어들 수 있습니다.
'전공공부 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| [알고리즘] 코사라주 알고리즘 (0) | 2021.12.29 |
|---|---|
| [알고리즘] 백트래킹 (0) | 2021.03.09 |
| [알고리즘] 다익스트라 알고리즘 (0) | 2021.03.03 |
| [알고리즘] 다이나믹 프로그래밍 (0) | 2021.02.04 |
| [알고리즘] 그리디 알고리즘 (1) | 2021.02.03 |