KMP법
브루트-포스법에서는 주어진 문자열 가장 앞 부분부터 찾고자하는 문자열을 문자단위로 비교하면서 다를경우 그 전까지 찾았던 정보를 더 이상 사용하지 않고 주어진 문자열에서 위치를 1칸 이동하여 다시 비교를 하면서 문자열 검색을 수행했다. 그렇기에 항상 찾고자하는 문자열 가장 앞 부분부터 비교해야하는 작업을 수행해야하기에 효율적이지 못했다.
KMP법에서는 이러한 부분들을 개선하여 비교하는 과정에서 결과를 효율적으로 사용할 수 있는 알고리즘이다. 어떻게 검색결과를 효율적으로 사용하는지 다음을 통해서 확인해나간다.
KMP법은 브루트-포스법보다 상대적으로 복잡하고 보이어-무어법보다 성능이 같거나 오히려 떨어져 잘 사용되지 않는 알고리즘이라 한다.
이해를 위해서 원본 문자열을 'text' , 검색할 문자열을 'pattern'이라 부를 것이다.
위에 그림에 대해서 설명하면 브루트-포스법과 동일하게 text에 0번 인덱스와 pattern에 0번 인덱스를 대응시킨 후 문자단위로 비교해가는 것이다. 그리고 비교 후 다른 부분이 발생할 경우 기존 브루트-포스법은 기존까지 검색한 결과를 활용하지 않고 text 시작 위치를 1 이동하여 다시 처음부터 비교를 하면서 검색하는 알고리즘이다. 그에비해 KMP법은 상황에따라 검색한 결과를 활용하여 검색 시작위치를 유동적으로 이동시킬 수 있는 알고리즘이다.
그러나 실제로 다른 부분이 발생할 때마다 별도로 text에서 다음번 시작 위치를 구하면서 수행하는 것은 효율적이지 못할 것이다.
표를 만들어 활용하자
위에 그림을 살펴보면 결과적으로 text와 pattern 사이 몇 개의 문자가 일치했는가에 따라서 다음번 검색을 시작할 text에 위치가 지정된다고 볼 수 있다. 그렇기에 이를 표 형태로 만들어둔 후 비교할 시 일치하는 문자의 수를 표에 대응시켜 위치를 이동시킬 수 있다.
이때, 표를 만들기 위해서는 pattern 내부적으로 중복되는 문자열이 있는지를 확인해야한다.
예를들어 ABCABD라는 패턴과 ABCABBB / ACCABCC 라는 텍스트가 주어졌다고 해보자
--------------------------------
TEXT1 : ABCACBB
TEXT2 : ACCABCC
PATT : ABCABD
--------------------------------
이때, 맨 앞은 모두 A로 동일하다. 그 이후 2번째 문자를 비교했을 경우 TEXT1은 일치하기에 다음문자들을 계속 비교해가며 5번째 문자까지 갈 것이다. 그에비해 TEXT2와 비교는 2번째 문자까지 비교 후 끝이난다.
여기서 볼 것이 pattern에서 현재 1,2,3문자는 모두 다르다. 그렇기에 2번째에서 끝날경우 TEXT2에 시작위치를 다음으로 이동해서 C-A를 비교해야한다. 그 이유는 항상 비교를 위해서는 시작 문자인 A부터 비교를 해야하지만 현재 비교한 부분에서는 시작할 문자인 A에서 끝난 것이 아니기에 위치를 1칸 이동시켜 실제 비교를 해야만 한다.
그에비해 TEXT1,PATT은 ABCA까지 일치한다. 이경우 그전까지 text에서 비교했던 문자들이 A-B-C-A 순으로 되어있음을 알 수 있다. 그렇기에 앞에 ABC를 건너띄고 text 시작점을 A-B-C-A 에 맞추고 2번째 문자부터 검색할 수 있다.
static int kmpMatch(String txt, String pat){
int pt = 1;
int pp = 0;
int[] skip = new int[pat.length() + 1];
skip[pt] = 0;
while(pt != pat.length()){
if(pat.charAt(pt) == pat.charAt(pp))
skip[++pt] = ++pp;
else if( pp == 0)
skip[++pt] = pp;
else
pp = skip[pp];
}
System.out.println("=================");
System.out.println("표 만든 결과");
for(int i = 0 ; i < skip.length ; i++){
System.out.printf("%-3d",i);
}
System.out.println();
for(int i = 0 ; i < skip.length ; i++){
System.out.printf("%-3d",skip[i]);
}
System.out.println("\n=================");
pt = pp = 0;
while(pt != txt.length() && pp != pat.length()){
if(txt.charAt(pt) == pat.charAt(pp)){
pt++;
pp++;
} else if(pp == 0)
pt++;
else
pp = skip[pp];
}
if(pp == pat.length())
return pt - pp;
return -1;
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
System.out.print("텍스트 : ");
String s1 = s.next();
System.out.print("패턴 : ");
String s2 = s.next();
int idx = kmpMatch(s1,s2);
if(idx == -1)
System.out.println("텍스트에서 패턴을 찾지 못했습니다.");
else{
int len = 0;
for (int i = 0 ; i < idx ; i++){
len += s1.substring(i,i+1).getBytes().length;
}
len += s2.length();
System.out.println((idx + 1) + "번째 문자부터 일치합니다.");
System.out.println("텍스트: " + s1);
System.out.printf(String.format("패 턴: %%%ds\n", len),s2); // [(%%) -> % / (%d)<-len] => printf("패 턴: %(len)s",s2)
}
}
다음과 같이 표를 만든 결과를 함께 첨부해봤다. 위에서도 설명한 것과 같이 pattern 내부적으로 중복된 문자열이 있는지에 대해서 KMP법을 활용하여 pattern 자체적으로 확인을 한다. 다른 부분은 브루트-포스법과 동일하며, KMP법은 단순 검색결과를 활용하여 다음 시작위치를 어디로 할 것인지를 정할 수 있으며, 이를 위해 표를 활용하는 것이다.
우선 어떻게 활용을 하는지를 살펴보면
PATT : ABCABD라고 했을 경우
=======================
맞은 문자수 : 0 1 2 3 4 5 6 <<< 가시성을 위해서 경우를 색상으로 구분하여 적용해봤다.
다음 검색할 위치 : 0 0 0 0 1 2 <<< 실제 배열이기에 0번 인덱스가 pattern 시작문자
=======================
1번 문자 다를 경우(0) : 시작부터 다르기에 무조건 1칸 이동하여 처음부터 문자 비교한다.
--------------------------------------------------------------------------------------------------------------------------------------------------------
2번 문자 다를 경우(1) : A는 맞았는데 2번째 문자에서 다를경우 현재 1,2번 문자가 다른 상태이다. 그렇기에 1칸을 이동해도 서로다르다. 즉, 실제 TEXT에 대해서는 직접 확인을 해야한다는 것이다.
A B C A B D
A B C A B D
--------------------------------------------------------------------------------------------------------------------------------------------------------
3번 문자 다를 경우(2) : 앞에 2개 문자가 맞았으나 3번째 문자에서 틀렸을 경우 시작점을 해당 위치로 옮겼을 경우 pattern의 시작점과 다르다. 즉, 실제 text에 위치가 무엇인지 직접 확인을 해야한다.
A B C A B D
A B C A B D
--------------------------------------------------------------------------------------------------------------------------------------------------------
4번 문자 다를 경우(3) : 이 경우도 실제 text에서는 pattern에 첫 번째 문자와 다를 수도 있기에 직접 확인을 해야한다.
A B C A B D
A B C A B D
--------------------------------------------------------------------------------------------------------------------------------------------------------
5번 문자 다를 경우(4) : 이 경우 4번 문자까지 맞게되면 4번 문자는 시작 문자와 중복되기에 text에서 문자가 다른 위치를 pattern에 2번부터 비교하면 된다. 1번위치는 이미 text 현재 위치 -1에서 맞다고 확인이 되었기 떄문이다.
A B C A B D
A B C A B D
--------------------------------------------------------------------------------------------------------------------------------------------------------
6번 문자 다를 경우(5) : 이 경우 1,2번 문자가 4,5번에서 중복적으로 발생하고 5번까지 맞았으면 현재 text에서 다른 위치 앞에 2개는 pattern에 시작 2개 문자와 일치하는 것을 알고 있기에 3번 문자부터 비교를 하면된다.
A B C A B D
A B C A B D
--------------------------------------------------------------------------------------------------------------------------------------------------------
마지막은 현재 pattern 길이가 6이기에 여기까지 맞으면 문자열 검색 찾게 된 것이다.