문자열 검색 Brute Force Method

Brute Force Method

브루트 포스법은 선형 검색을 단순하게 확장한 알고리즘이다.

브루트 포스법은 패턴을 처음부터 문자 하나씩 비교해 나가는 방식이다.

문자들을 비교해 나가며 일치할 시 종료하고 인덱스를 반환한다.

자바에서 자공하는 indexOf 메소드를 이용해 문자열을 검색할 수 있다.

 

import java.util.Scanner;
 
public class BFmatch {
    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())
            return pt - pp;
        return -1;
    }
    
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        
        System.out.print("텍스트 : ");
        String s1 = stdIn.next();
        
        System.out.print("패턴 : ");
        String s2 = stdIn.next();
        
        int idx = bfMatch(s1, s2);
        
        if (idx == -1)
            System.out.println("텍스트에 패턴이 없습니다.");
        else {
            // 일치하는 문자 바로 앞까지의 길이를 구합니다.
            int len = 0;
            for (int i = 0; i < idx; i++) 
                len += s1.substring(i, i + 1).getBytes().length;
            len+=s2.length();
            
            System.out.println((idx+1) + "번째 문자부터 일치합니다.");
            System.out.println("텍스트 :"+ s1);
            System.out.printf(String.format("패턴 : %%%ds\n", len), s2);
        }
    }
}