[탐색 알고리즘] 보이어-무어(Boyer-Moore) 방법으로 문자열 탐색하기

Boyer-Moore 탐색 알고리즘

보이어무어 탐색법은 브루트포스 탐색 및 KMP 탐색보다 효율이 좋은 알고리즘이다.

 

 

 

 

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

	for(txtIndex = 0; txtIndex <= Character.MAX_VALUE; txtIndex++){
		skip[txtIndex] = patLen;
	}

	for(txtIndex = 0; txtIndex < patLen - 1 ; txtIndex++){
		skip[pattern.charAt(txtIndex)] = patLen - txtIndex - 1;
	}

	while(txtIndex < txtLen){
		pattIndex = patLen - 1;
		while (text.charAt(txtIndex) == pattern.charAt(pattIndex)) {
			if(pattIndex == 0){
				return txtIndex;
			}
			pattIndex--;
			txtIndex--;
		}
//            pt += (skip[txt.charAt(pt)] > patLen - pp) ? skip[txt.charAt(pt)] : patLen - pp;
		txtIndex += Math.max(skip[text.charAt(txtIndex)], patLen - pattIndex);
	}
	return -1;
}