[탐색 알고리즘] 브루트포스법(brute force)으로 문자열 탐색하기

브루트포스 알고리즘

브루트포스법은 문자열을 검색하는 방법 중 기본적인 알고리즘이다. 영어를 직역하면 [brute] - 잔혹한, 악랄한, [force] - 힘, 폭력 이니까 "강제적인 힘"으로 탐색하는 알고리즘 혹은 무차별적으로 대입해 찾아내는 알고리즘이라고 보면 되겠다. 

이 알고리즘은 처음부터 끝까지 전부 대입해보는 방법이 주요 특징이다. 비밀번호 숫자 4자리를 해킹하는 상황이라면, 0000부터 9999까지 전부 넣어보고 열리는 것을 찾는 방식이다.

 

 

Java code

int search(String text, String pattern){
	//검색할 커서
	int textIndex = 0;
	int patternIndex = 0;

	while(textIndex != text.length() && patternIndex!= pattern.length()){ 	//a: 반복조건
		if(text.charAt(textIndex) == pattern.charAt(patternIndex)){	//b: 문자열 일치
			textIndex++;
			patternIndex++;
		} else {					//c: 문자열 불일치
			textIndex = textIndex - patternIndex + 1;				
			patternIndex = 0;
		}
	}
	//d: 검색성공
	if(patternIndex == pattern.length()){
		return textIndex - patternIndex;
	}
	//e: 검색실패
	return -1;
}

 

text에서 pattern을 검색하여 인덱스를 반환한다. pattern에 적합한 문자열이 여러개인 경우 가장 앞쪽의 인덱스를 반환한다. 찾는 대상이 없으면 -1을 반환한다.

 

• a : 문자열 검색 반복조건
  • textIndex != text.length() : text 길이만큼 index 이동시키기. 찾으려는 문자열보다 검색대상의 길이가 짧은 경우 반복문 빠져나간다
  • patternIndex != pattern.length() : pattern 길이만큼 index 이동시키기
• b : 검색할 문자가 일치하는 경우, 검색할 index를 1씩 증가시켜서 다음 문자열을 비교한다
• c : 검색할 문자가 일치하지 않는 경우
  • textIndex -> 검색한 문자열 개수만큼 초기화하고 1 증가
  • patternIndex -> 초기화
• d : 검색 성공시 인덱스 반환
• e : 찾는 단어가 없으면 -1 반환