KMP 알고리즘(2)

 지난 번에는 KMP 알고리즘의 패턴에 관해 알아보았다.

그럼 이번에는 그 패턴에서 구한 이동 위치 저장 배열을 가지고 어떻게 비교 문자열에 적용하는지 확인해보자.

패턴은 다음과 같다.

ABCDABA

비교할 문자열은 다음과 같다.

ABCDABCDABABCDCD

이 두 문자열을 비교할 것이다.

우선 코드로 살펴보자.

static void KMP(String str, String pattern){
	int []arr = getTable(pattern);
    char[] text = str.toCharArray();
    char[] pt = pattern.toCharArray();
    
    int j=0;
    for(int i=0;i<text.length;i++){
    	while(j>0&& text[i]!=pt[j])
        	j=arr[j-1];
        if(text[i]==pt[j]){
        	if(j==pattern.length()-1){
            	j=arr[j];
            }
            else{
            	j++;
            }
        }
        
   	}
}

패턴을 검사할 때랑 무언가 유사하다.

우선 이동 위치 저장 배열을 불러오고,

문자열과 패턴을 순회한다.

패턴과 이동 위치 저장 배열이다.

비교할 문자열이다. 

일단 첫문자부터 비교하기 때문에 i와 j는 0부터 시작한다.

A와 A는 같지만 j는 패턴의 길이-1과 같지 않기 때문에

j++해준다.

for문을 돌기에 i++이 되고, B도 같기 때문에 반복한다.

그럼 7번째는 어떨까?

j는 A를 가리키고 있고, i는 C를 가리키고 있다.

j>0이고 pt[j]!=text[i]인 상황이기 때문에 while 반복문을 통해 j=arr[j-1]을 실행한다.

j는 현재 6이고, j-1은 5이기 때문에 arr[j-1]을 확인한다. 

이때 arr[5]는 2이기 때문에 j에는 2가 할당된다.

while 문을 통해 text[i]와 pt[j]를 비교한다.

i와 j가 가리키는 문자가 같기 때문에 while 문을 탈출한다.

이후 비교를 하고, ABCDABA 패턴을 찾게 된다.

이때 j는 pattern.length()-1 이고

이후 j에는 arr[j]의 값을 할당한다. 이후를 다시 검사하는 것이다.

만약 여기서 패턴의 접미사가 접두사와 반복되는 부분이 겹친다면, 즉 위의 상황이면

다시 1번 인덱스부터 비교해도 된다는 것이다.

어떻게 이렇게 찾을 수 있는지 알아보자.

 

우선 패턴과 이동 위치 저장 배열이다.

이동 위치 저장 배열은 해당 위치로 가면 패턴이 다시 반복되는 거 체크 가능해! 라는 의미다.

즉 A B A에 저장되어 있는 건 

A 1 일 경우

A는 앞에서 반복하니까 1번 인덱스로 가서 비교해서 맞으면 패턴 매칭 진행해! 라는 말이고

B 2 일경우

0 번 1번 인덱스가 반복하는 거 확인했으니까 2번 인덱스로 가서 비교해서 맞으면 패턴 매칭 진행해! 라는 말이다.

위에서 진행한 것을 예로 들면

 

ABCDAB까지는 맞고, C와 A가 다르다면

arr[j-1]에 할당된 위치로 가서 다시 비교하라는 의미이다.

j는 6에서 2로 바뀌고 다음과 같이 비교하게 된다.

이렇게 겹치는 부분도 6개에서 다시 2개로 바뀌었다고 생각하고 다시 비교하는 것이다.

이것이 바로 pattern에서 접두사와 접미사가 겹치는 부분의 길이를 구한 이유이다.

접두부분과 접미부분이 겹치는 부분이 있다면 굳이 다시 처음부터 검토할 필요없이

겹치는 부분은 건너뛰고 검사를 시작하는 개념인 것이다.

코드만 보면 이해하기 힘들 수 있지만 과정을 그림을 그려 이해해보면 조금은 알아갈 수 있을 것이다.

 

라고 이해했다.