문자열 검색(String Search) 알고리즘 1. 브루트-포스법

문자열 검색(String Search) 알고리즘

주어진 문자열에서 찾고자 하는 문자열이 있을 때, 해당 문자열의 위치를 찾는 알고리즘.

 

브루트-포스법이란?

텍스트의 맨 앞부터 한 문자씩 살펴보며 패턴의 첫 자와 일치하는 문자를 찾고,

일치한다면 그 문자부터 패턴의 나머지와 일치하는지 검사한다.

불일치한다면 텍스트의 다음 문자부터 다시 검사한다.

선형검색을 확장한 알고리즘으로, 단순법, 소박법이라고도 한다.

 

자바로 구현하기

package algorithm;

public class BFMatch {
	//브루트-포스법으로 문자열을 검색하는 메서드
	static int bfMatch(String txt, String pat) {
		int pt = 0;	//txt 커서
		int pp = 0;	//pat 커서
		
		//텍스트 커서 OR 패턴 커서가 끝까지 도달하면 검색 종료
		//즉, 반복 조건은 텍스트 커서 AND 패턴 커서가 끝까지 도달하지 않았을 때
		while(pt!=txt.length() && pp!=pat.length()) {
			//만약 텍스트 커서에 위치한 문자와 패턴 커서에 위치한 문자가 같다면
			if(txt.charAt(pt)==pat.charAt(pp)) {
				//그 다음 문자도 같은지 보기 위해 두 커서의 값을 증가시킨다.
				pt++;
				pp++;
			//텍스트 커서에 위치한 문자와 패턴 커서에 위치한 문자가 같지 않다면
			} else {
				//텍스트 커서를 되돌리기 위해 패턴 커서 값을 뺀 후, 다음으로 넘어가기 위해 1을 더 한다.
				pt = pt-pp+1;
				//패턴의 처음부터 다시 검사해야하므로 패턴 커서는 0으로 바꾼다.
				pp = 0;
			}
		}
		
		if(pp==pat.length()) {	//검색 성공
			//매칭이 시작되는 지점을 반환하기 위해 pt-pp
			return pt-pp;
		}
		return -1;	//검색 실패
	}

}