코딩테스트 : KMP
[KMP 알고리즘 (커누스-모리스-프랫 Knuth-Morris-Pratt)]
<알고리즘 문제해결 전략 2> 권 - 20장 문자열에서 KMP 알고리즘을 자바로 구현해 보았다. (p643~653)
주어진 문자열 H가 다른 문자열 N을 포함하는 여부를 확인하고, 포함한다면 일치하는 부분 문자열의 시작위치를 반환하는 문제이다.
1. H와 N을 하나하나 다 비교해본다.
public class SimpleStringFind {
public static void main(String[] args) {
SimpleStringFind sSF = new SimpleStringFind();
String full = "elephaele";
String part = "ele";
System.out.println(Arrays.toString(new List[]{sSF.naiveSearch(full, part)}));
}
public List<Integer> naiveSearch(String full, String part) {
List<Integer> index = new ArrayList<>();
for (int begin=0; begin <= full.length()-part.length(); begin++) {
boolean matched = true;
for (int i=0; i<part.length(); i++) {
if(full.charAt(begin+i)!=part.charAt(i)) {
matched = false;
break;
}
}
if(matched) index.add(begin);
}
return index;
}
}
naiveSearch() 메서드의 반환타입은 List
그런데 이렇게 풀 경우, 어떤 문자열이 주어졌냐에 따라 시간 복잡도가 무지막지하게 증가할 수 있다. 예를 들어, ‘a’문자 2만개만으로 이루어진 문자열 H에서 ‘a’만 1천개로 이루어진 문자열 N의 시작위치를 반환하는 문제가 있다면…
H의 모든 위치의 수, 즉 H의 길이가 정답이라는 것을 직관적으로 쉽게 알 수 있다. 하지만 위 코드는 그런 건 모른다. 우직하게 하나하나 다 따져가면서 시간복잡도를 구한다. 따라서 O(2만 * 1천) = O(2천만)이라는 엄청난 시간이 걸리게 된다.
2. [KMP 알고리즘]으로 풀어보자.
<알고리즘 문제해결 전략 2>에 나온 문제를 살펴보자. 주어진 문자열 H안에 “aabaabac“라는 문자열 N이 포함되어 있는지 예시를 삺펴보자.
문자열 N의 길이는 8인데, 위 그림에서 보듯 마지막 글자가 맞지 않았다. 위 1번 코드에서처럼 N을 1칸씩 옮겨가면서 주어진 문자열 H와 비교해보자. 그러면 i+3, i+6번째에서는 N과 H의 일부분이 일치할 가능성이 있다는 것을 알 수 있다. 여기에 규칙성이 있을까?
설명을 길게 잘 할 자신은 없어, 한 가지만 예를 들어보겠음. 문자열 N에서 맨 마지막 1글자만 빼고 앞의 7글자(aabaaba)가 H의 일부와 맞을 때, 7글자 내부에는 일치하는 접두사, 접미사가 존재한다. 그게 A, AABA이다.
이 2개 중 기억해야 할 것은 AABA의 길이 = 4이다. N과 H의 일부분이 7개까지 동일해서 “드디어 일치하는건가?”하고 기대감이 차 있다가 마지막 글자가 같지 않을 때,
실망만 하지 말고 N과 비교를 다시 시작할 H의 새로운 위치는 4칸 이동해서 시작하면 된다는 뜻이다. 이 부분이 바로 책에서 설명하는 “부분 일치 테이블”이다.
public class KMPsearch {
public static void main(String[] args) {
String target = "weeleephae";
String pattern = "eelee";
kmpSearch(target, pattern);
}
public static void kmpSearch(String target, String pattern) {
int pL = pattern.length(), tL = target.length();
int[] pi = getPi(pattern);
int begin = 0, matched = 0;
while (begin + pL <= tL) {
if (matched<pL && pattern.charAt(matched)==target.charAt(begin+matched)) {
matched++;
if (matched == pL) {
System.out.println(begin);
}
}
else {
if (matched==0) {
begin++;
}
else {
begin = begin + matched - pi[matched-1];
matched = pi[matched - 1];
}
}
}
}
public static int[] getPi(String pattern) {
int pL = pattern.length();
int[] pi = new int[pL];
int begin = 1, matched = 0;
while (begin + matched < pL) {
if (pattern.charAt(matched)==pattern.charAt(begin + matched)) {
matched++;
pi[begin + matched - 1] = matched;
}
else {
if (matched==0) {
begin++;
}
else {
begin = begin + matched - pi[matched - 1];
matched = pi[matched - 1];
}
}
}
return pi;
}
}
getPi() 메소드는 주어진 문자열 H의 일부가 다른 문자열 N과 부분적으로만 일치할 때 - 즉, 결국은 완전히 일치하지 않아서 다시 비교를 시작할 위치를 계산해서 반환해준다.
kmpSearch()메소드는 H의 일부와 N이 일치할 때, 그 시작위치를 반환한다.
이 두 메소드는 사실 동일한 계산방식이 적용된다. 즉, 비교 대상인 두 문자열이 주어졌을 때, 서로 겹치는(동일한) 문자의 수에 따라 -> 다음 번 비교를 시작할 위치를 찾는다는 것이다.
이렇게 KMP알고리즘을 구현하면 문자열의 글자 하나하나를 다 확인할 필요가 없어져서 시간복잡도가 줄어든다.
댓글남기기