JAVA 알고리즘 - 브루트포스 알고리즘을 이용한 문자열 검색

브루트포스는 모든 경우의 수를 다 검사하는 알고리즘이다

이번에는 이 브루트포스 알고리즘을 이용해서 문자열을 검색해보자.

 

문자열 검색

- 어떤 문자열 안에 다른 문자열이 들어 있는지 알아보고 있다면 위치를 찾아내는 것

ex) "Hello" 에서 ll검색 -> 성공

 

브루트포스 예시

- "ABABCDEFGHA"에서 "ABC" 검색

-> 1) 맨앞에 A부터 시작하는 3개의 문자와 "ABC"가 일치하는지 검사 -> ABA는 ABC와 다르니 실패

-> 2) BAB를 검사 -> 실패

-> 3) ABC를 검색 -> 모두 일치

 

package 브루트포스;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class 브루트포스1 {
	
	static int bfMatch(String txt, String pat) {
		int pt = 0;    // txt 커서
		int pp = 0;	   // pat 커서
		
		while(pt != txt.length() && pp != pat.length()) {
			if(txt.charAt(pt) == pat.charAt(pp)) {
				pt++;
				pp++;
			}else {
				pt = pt - pp + 1;
				pp = 0;
			}
		}
		
		if( pp == pat.length()) {
			System.out.println(pt);
			System.out.println(pp);
			return pt - pp; //검색 성공
		}
		return -1; //검색 실패
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s1 = br.readLine();
		String s2 = br.readLine();
		
		int idx = bfMatch(s1,s2);
		
		if(idx == -1) {
			System.out.println("패턴이 없음");
		}else {
			System.out.println("위치는 : " + (idx));
		}
	}
}

 

-> s1과 s2 각각 입력문자, 찾을문자를 할당하고 브루트포스 메서드의 파라미터로 넘겨준다.

-> pt와 pp라는 변수는 각 받은 문자열의 인덱스를 지정하기위해 선언하고 0으로 초기화 했다.

-> 루프를 통해 pt와 pp가 각 문자열의 길이와 다르면 검사를 시행한다.

-> 첫번째를 루프를 보면 txt.charAt(0) == pat.charAt(0)  ->  즉 ABABC~의 A와 , ABC의 A가 일치하므로 pt,pp를 1올려준다.

-> 하지만 AB까지는 맞지만 3번째에서 A와 C가 다르므로 else문으로 가는데

-> 여기서 pt는 2 - 2 + 1 -> 1이되고 pp는 0으로 바꿔준다 -> 대상문자열의 다음 인덱스부터 검색하기 위함