[Algorithm] KMP(Knuth–Morris–Pratt)알고리즘 java

흔히 문자열검색은 전체문자열의길이가 짧은경우 2중 반복문으로 쉽게구현가능하나,
최악의경우 시간복잡도는 (전체문자열길이N) x (찾으려는문자열길이M) 에 비례한 O(NM) 이 된다.
이를 효율적으로 계산하고자 만들어진 KMP알고리즘은 순차적으로 검색하며, 검색 실패할경우 접두사와 접미사가 일치하는 문자갯수만큼 건너뛰며 검색하는, O(N+M) 의 시간복잡도를 가지는 알고리즘이다.

우선 KMP알고리즘에는 실패함수(failure function)가 존재한다.
실패함수테이블은 전체문자열 검색에서 실패할경우 얼마나 j(K문자열의인덱스)를 건너 뛰어서 찾을 것인지 계산할때 쓰인다.

이 실패함수는 다음과같다.
이제 이 테이블이 어떻게 작성되는지 파악해보자.
이제 실패테이블을 만드는 실패함수를 자바코드로 작성해보면 이렇다.

int[] makeFailureTable(String K) {
	int[] F = new int[K.length()];
	F[0] = 0;
	int j = 0;
	for(int i = 1 ; i < F.length ; i++) {
		while(j > 0 && K.charAt(i) != K.charAt(j)) {
        		//실패함수테이블을 이용하여 j = 0 부터가 아닌 건너뛰며 검색한다.
			j = F[j - 1]; 
		}
		if(K.charAt(i) == K.charAt(j)) F[i] = ++j;
	}
	return F;
}

마지막으로 전체 문자열S에서 문자열 K를 찾는 KMP알고리즘을 만들어보자.
놀라운점은 앞서 만든 실패함수 작동방식과 KMP알고리즘의 작동방식이 똑같다. 다른점은 S, K의 각각 i, j번째 문자가 같을때, K문자의 전체와 같은지(j인덱스가 K.length-1 인지) 체크한뒤
사용할 이벤트를 작성, 그리고 j 값의 수정을 하면된다.
아래는 KMP알고리즘 코드이다.

void kmp(String S, String K) {
	int[] F = makeFailureTable(K);
	int S_size = S.length();
	int K_size = K.length();
	int j = 0;
	for(int i = 1 ; i < S_size ; i++) {
		while(j > 0 && S.charAt(i) != K.charAt(j)) {
        //실패함수테이블을 이용하여 j = 0 부터가 아닌 건너뛰며 검색한다.
			j = F[j - 1];
		}
		if(S.charAt(i) == K.charAt(j)) {
			if(j == K_size - 1) { //문자열이 전부 일치하는가
				System.out.println(i - K_size + 2 + " 번째(1번째부터)에서 검색 성공");
				j = F[j]; //이후값들에대해 다시 조사
			}else {
				j++;
			}
					
		}
	}
}

아래부분을 제외하고는 실패함수코드와 같은 코드이다.

if(S.charAt(i) == K.charAt(j)) {
	if(j == K_size - 1) { //문자열이 전부 일치하는가
		사용할 이벤트(찾은위치를 출력하던지..)
		j = F[j]; 
	}else {
		j++;
	}
					
}

보면 같은문자를 찾았을때 K문자열 전체와 일치하는경우,
j값을 F[j]로 수정하는데, 실패함수 F의 정의가 접두사와 접미사가 일치하는값 이므로, F[j]만큼 j=0부터가 아닌 건너뛰겠다는것이다. 이부분이 빠질려면 i값도 뒤로 후퇴해야한다.
KMP알고리즘의 핵심이므로 무조건 사용해야하는 방식이다.

마지막으로 S = K인 문자열인경우 검색이 어떻게진행이될까?
답은 검색실패이다. 이유는 S에서쓸 i는 1부터 시작하지만
K에서 쓰는 j는 0부터 시작하기때문이다.
이를 개선하려면 문자열비교시 S앞에 아무문자하나를 추가한뒤
K문자열을 찾는 방식으로 하면되겠다.

KMP알고리즘의 전체 코드는 아래와같다.

public class KMP {	
	static int[] makeFailureTable(String K) {
		int[] F = new int[K.length()];
		F[0] = 0;
		int j = 0;
		for(int i = 1 ; i < F.length ; i++) {
			while(j > 0 && K.charAt(i) != K.charAt(j)) {
				//실패함수테이블을 이용하여 j = 0 부터가 아닌 건너뛰며 검색한다.
				j = F[j - 1];
			}
			if(K.charAt(i) == K.charAt(j)) F[i] = ++j;
		}
		return F;
	}
	static void kmp(String S, String K) {
		int[] F = makeFailureTable(K);
		int S_size = S.length();
		int K_size = K.length();
		int j = 0;
		for(int i = 1 ; i < S_size ; i++) {
			while(j > 0 && S.charAt(i) != K.charAt(j)) {
				//실패함수테이블을 이용하여 j = 0 부터가 아닌 건너뛰며 검색한다.
				j = F[j - 1];
			}
			if(S.charAt(i) == K.charAt(j)) {
				if(j == K_size - 1) { //문자열이 전부 일치하는경우
					System.out.println(i - K_size + 2 + " 번째(1번째부터)에서 검색 성공");
					//접두사와 접미사가 일치하는갯수만큼 건너 뛰어서 검색한다.
					j = F[j]; //이후값들에대해 다시 조사
				}else {
					j++;
				}
					
			}
		}
	}

	public static void main(String[] args) {
		String S = "abc abca abcab abcaba abcaba";
		String K = "abcaba";
		kmp(S, K); // 16, 23번째검색성공
		kmp(" abccabc", "abccabc"); // 2번째검색성공
	}
}