KMP 알고리즘
KMP 알고리즘은 주어진 문자열에서 특정 문자열이 몇번 나오는지 찾기위한 알고리즘으로 O(N)의 시간 복잡도를 갖습니다.
이는 이중for문을 돌려 비교하는 O(N*N)보다 훨씬 빠른 속도인데요
이런 KMP 알고리즘을 위해 우리는 접두사와 접미사가 일치하는 최대 길이를 구하여야 합니다.
보통 접두사와 접미사가 일치하는 최대 길이를 구하기 위한 함수를 실패함수라고 하는데요.
실패함수는 접두사와 접미사를 가지고 매칭이 실패했을때 얼마나 점프하여 주어진 문자열과 특정문자열을 다시 비교할 것인가 알려주는 함수 입니다.
| j | i | ||||||||
| pattern | A | B | A | C | D | C | A | B | A |
| PI | 0 |
특정 문자열이 ABACDCABA일때 최대 길이는 어떻게 구할까요?
먼저 알아야 할것이 있습니다.
1. i와 j가 가리키는 값이 일치하는 경우 i위치의 PI에 j의 index(위치)+1의 값을 넣어주고 i와 j모두 한칸 앞으로 간다.
2. i와 j가 가리키는 값이 다르다면 j가 한칸뒤의 index로 가서 그 위치의 PI에 써있는 값으로 이동한다.
이 두개만 알면됩니다. 위의 예제를 보면
| j | i | ||||||||
| pattern | A | B | A | C | D | C | A | B | A |
| PI | 0 | 0 |
i와 j가 다르기 때문에 i위치에 0을 넣습니다.
| j | i | ||||||||
| pattern | A | B | A | C | D | C | A | B | A |
| PI | 0 | 0 | 1 |
다음은 j와 i가 같으니 i위치에 j+1값을 넣습니다.
이후 j와 i가 한칸씩 이동 합니다.
| j | i | ||||||||
| pattern | A | B | A | C | D | C | A | B | A |
| PI | 0 | 0 | 1 |
j는 B고 i는 C입니다 따라서 j가 한칸뒤로 이동하여 PI위치로갑니다.
| j | i | ||||||||
| pattern | A | B | A | C | D | C | A | B | A |
| pI | 0 | 0 | 1 | 0 |
i와 j가 다르기때문에 PI에 0을넣고 i는 한칸 앞으로 갑니다.
이런식으로 C까지 한다면
| j | i | ||||||||
| pattern | A | B | A | C | D | C | A | B | A |
| pI | 0 | 0 | 1 | 0 | 0 | 0 |
가 됩니다.
이때 i와 j가 같으니까 i위치에 j+1을 넣고 한칸씩 앞으로 전진하면
| j | i | ||||||||
| pattern | A | B | A | C | D | C | A | B | A |
| pI | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
가 될테고 이런식으로 끝까지 하게되면
| j | i | ||||||||
| pattern | A | B | A | C | D | C | A | B | A |
| pI | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 2 | 3 |
이 됩니다.
따라서 ABACDCABA를 실패함수어 넣고 돌리면 001000123이라는 PI를 구할수 있을 것 입니다.
KMP함수는 PI를 사용 하여 계산을 하게 되는데요
다른 예제를 사용해서 말씀드리자면
| i | |||||||||
| parent | A | B | A | C | A | B | A | B | A |
| j | |||||||||
| pattern | A | B | A | ||||||
| PI | 0 | 0 | 1 |
| i | |||||||||
| parent | A | B | A | C | A | B | A | B | A |
| j | |||||||||
| pattern | A | B | A | ||||||
| pI | 0 | 0 | 1 |
pattern이 parent에 한번 나왔네요 이럴경우 아래 와 같이 i는 증가시키고 j는 현재위치의 PI로 가서 다시 비교를 시작 하게 됩니다.
| i | |||||||||
| parent | A | B | A | C | A | B | A | B | A |
| j | |||||||||
| pattern | A | B | A | ||||||
| PI | 0 | 0 | 1 |
그 이유는 pattern이 parent에서 몇번 반복되는지 알기위해 중복된값을 찾아야 하기 때문인데요.
i와 j가 다르므로 j는 PI[j-1]로 가게 됩니다.
| I | |||||||||
| parent | A | B | A | C | A | B | A | B | A |
| J | |||||||||
| pattern | A | B | A | ||||||
| PI | 0 | 0 | 1 |
위의 방식을반복하여 계속 수행을 하다보면 pattern은 parent에 3번 반복된다는 것을 알 수 있습니다.
위의 내용을 코드로 작성해 보겠습니다.
import java.util.Iterator;
public class kmpAlgo {
public static void main(String[] args) {
System.out.println(KMP("ABACABABA","ABA"));
}
static int[] Pi(String pattern) {
int[] pi = new int[pattern.length()];
int j = 0;
for (int i = 1; i < pattern.length(); i++) {
// i와 j의 값이 다르다면 i와j가 맞을때까지 j보다 하나전 index의 pi값으로 j를 옮긴다
while (0 < j && pattern.charAt(i) != pattern.charAt(j)) {
j = pi[j - 1];
}
// i와 j가 같다면 i위치의 pi에 j의 index보다 1큰 값을 넣어준다
if (pattern.charAt(i) == pattern.charAt(j)) {
pi[i] = ++j;
}
}
return pi;
}
static int KMP(String parent, String pattern) {
int[] pi = Pi(pattern);
int j = 0;
int answer = 0;
for (int i = 0; i < parent.length(); i++) {
while (j > 0 && parent.charAt(i) != pattern.charAt(j)) {
j = pi[j - 1];
}
if (parent.charAt(i) == pattern.charAt(j)) {
if (j == pattern.length() - 1) {
answer++;
j = pi[j];
} else {
j++;
}
}
}
return answer;
}
}
사실 KMP알고리즘은 이해하기 찔끔 어렵더라구요
그래도 한번 이해하고 나니 뿌듯하내요~.~