브루트-포스법

• 문자열 검색의 기초 알고리즘
• 브루트-포스법은 선형 검색을 확장한 알고리즘으로 단순법, 소박법이라고도 한다.
• 이미 검사를 진행한 위치를 기억하지 못하므로 효율은 좋지 않다.
  • 다른 문자를 만나면 패턴에서 문자를 검사했던 위치 결과를 버리고 다음 텍스트의 위치로 1칸 이동한 다음 다시 패턴의 첫 번째 문자부터 검사한다.

//브루트-포스법으로 문자열을 검색
 
//여러 개라면 가장 앞쪽에 있는 인덱스 반환
static int bfMatch(String txt, String pat) {
    int pt = 0;            //텍스트를 스캔하는 변수
    int pp = 0;            //패턴을 스캔하는 변수
    
    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;                //검색 실패
}
 
//여러 개라면 가장 뒤쪽에 있는 인덱스 반환
static int bfMatchLast(String txt, String pat) {
    int pt = txt.length() - 1;
    int pp = pat.length() - 1;
    
    while (pt >= 0 && pp >= 0) {
        if (txt.charAt(pt) == pat.charAt(pp)) {
            pt--;
            pp--;
        } else {
            pt = pt + (pat.length() - pp) - 2;
            pp = pat.length() - 1;
        }
    }
    if (pp < 0) {
        return pt + 1;
    }
    return -1;
}