[탐색 알고리즘] KMP법으로 문자열 탐색하기

KMP법

KMP법은 브루트포스법을 개선한 탐색 알고리즘이다. 
브루트포스법은 검색하는 도중 문자열이 불일치하면 탐색을 시작한 바로 다음 위치로 이동해 다시 탐색하는 방법이다. 처음부터 끝까지 전부 탐색하기 때문에 그만큼 효율적이지는 못한 방법이다.

KMP법을 사용하면 검색이 실패하는 경우, 비교했던 결과를 활용해 다시 검색을 시작할 효율적인 위치를 조정할 수 있다. 

 

참고로 KMP법은 Kruth, Morris, Pratt 3명이 비슷한 시기에 고안했기 때문에 이름의 앞글자를 따서 붙여진 이름이다.

 

int search(String text, String pattern){
	int txtIndex = 1;
	int pattIndex = 0;
	int[] skip = new int[pattern.length() + 1];

	skip[txtIndex] = 0;
	while(txtIndex != pattern.length()){
		if(pattern.charAt(txtIndex) == pattern.charAt(pattIndex)){
			skip[++txtIndex] = ++pattIndex;
		} else if(pattIndex == 0){
			skip[++txtIndex] = pattIndex;
		} else {
			pattIndex = skip[pattIndex];
		}
	}

	txtIndex = pattIndex = 0;
	while(txtIndex != text.length() && pattIndex != pattern.length()){
		if (text.charAt(txtIndex) == pattern.charAt(pattIndex)) {
			txtIndex++;
			pattIndex++;
		}
		else if(pattIndex == 0){
			txtIndex++;
		} else {
			pattIndex = skip[pattIndex];
		}
	}
	if(pattIndex == pattern.length()){
		return txtIndex - pattIndex;
	}
	return -1;
}