09_문자열 검색

① 브루트-포스법

- 선형 검색을 확장한 알고리즘

- 문자열의 처음과 과 패턴(찾을 문자열)의 첫 문자가 겹치도록 놓고, 처음부터 순서대로 일치하는지 검사

  문자가 일치하면 계속해서 패턴과 텍스트의 문자를 검사하고, 

  다른 문자가 나오면 검사를 중단하고 패턴을 한 칸 뒤로 옮겨서 반복

- 검사를 진행한 위치를 기억하지 못하고, 계속 패턴의 처음부터 문자열을 비교하므로 효율이 좋지 않다.

- 텍스트에 패턴이 여러 개 있으면 가장 처음 발견한 곳의 인덱스를 반환한다.

static int bfMatch(String txt, String pat) {
    int txtPointer = 0;
    int patPointer = 0;

    while (txtPointer != txt.length() && patPointer != pat.length()) {
        if (txt.charAt(txtPointer) == pat.charAt(patPointer)) {
            txtPointer++;
            patPointer++;
        } else {
            txtPointer = txtPointer - patPointer + 1;
            patPointer = 0;     // 패턴 포인터는 다시 0으로 초기화
        }
    }
    // 검색 성공
    if (patPointer == pat.length())
        return txtPointer - patPointer;
    // 검색 실패
    return -1;
}

+) String.indexOf()

- int indexOf(String str, int fromIndex): fromIndex 생략 시, 처음부터 검사

- int lastIndexOf(String str, int fromIndex): fromIndex 생략 시, 맨 뒤부터 검사

 → fromIndex를 시작점으로, 맨 뒤에서부터 해당 단어를 찾기 시작함

 

+) UTF-8에서는 영문/숫자/기호는 1바이트, 한글/한자는 3바이트

- 반각(半角)문자: 전각문자의 절반을 폭으로 하는 문자  ex) 영문자, 아스키코드문자

- 전각(全角)문자: 문자 폭이 일반적인 영문자 고정폭의 2배정도 가지는 문자  ex) 한글, 한자

 

 

② KMP법

- Knuth, Morris, Pratt 가 거의 같은 시기에 고안해서 이름 앞 글자 각각 따서 명명

- 브루트-포스법과 다르게 중간 검사 결과를 효율적으로 사용하는 알고리즘 (브루트-포스법을 개선)

  → 텍스트와 패턴의 겹치는 부분을 찾아내어 검사를 다시 시작할 위치를 구함

  → 패턴을 최소의 횟수로 옮겨 알고리즘의 효율을 높임

- 몇 번째 문자부터 다시 검색을 시작할 지에 대한 값을 미리 '표'로 만들어 놓음

  → 패턴 안에서 중복되는 문자의 나열을 먼저 찾음 (KMP법 사용)

→ 브루트-포스법보다 복잡하고, Boyer-Moore법과 성능이 같거나 좋지 않아서 실제 프로그램에서는 거의 사용하지 않음

 

static int kmpMatch(String txt, String pat) {
    int txtPointer = 1;     //--패턴을 텍스트의 한 칸 뒤로 옮겨서부터 비교 시작해야하므로
    int patPointer = 0;
    int[] skip = new int[pat.length() + 1];     // 건너뛰기 표

    // 건너뛰기 표 만듦
    skip[txtPointer] = 0;
    while (txtPointer != pat.length()) {
        if (pat.charAt(txtPointer) == pat.charAt(patPointer))
            skip[++txtPointer] = ++patPointer;
        else if (patPointer == 0)   //-- 문자 다름 + pattern pointer의 위치 0
            skip[++txtPointer] = patPointer;
        else                        //-- 문자 다름 + pattern pointer의 위치 0이 아님
            patPointer = skip[patPointer];
            //-- 다음 시작할 때, 이 위치부터 검사 시작
    }

    // 검색
    txtPointer = patPointer = 0;
    while (txtPointer != txt.length() && patPointer != pat.length()) {
        if (txt.charAt(txtPointer) == pat.charAt(patPointer)) {
            txtPointer++;
            patPointer++;
        } else if (patPointer == 0) {
            txtPointer++;
        } else {
            patPointer = skip[patPointer];
        }
    }

    if (patPointer == pat.length())
        return txtPointer - patPointer;
    return -1;
}

 

③ Boyer-Moore법 (보이어-무어법)

- KMP법보다 효율이 더 우수해서, 문자열 검색에 널리 사용하는 알고리즘

- 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하며, 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 

  옮길 크기를 정함

  → 뒤에부터 검사해서 패턴에 들어 있지 않은 문자를 발견하면, 해당 위치까지 건너뛸 수 있음

- 각각의 문자를 만났을 때 패턴을 옮길 크기를 저장할 표를 미리 만들어야 한다.

  → 패턴에 존재할 수 있는 모든 문자의 옮길 크기를 계산하고 저장해야 하기 때문에, 건너뛰기 표의 요소 개수는

     『Character.MAX_VALUE + 1』 이다.

static int bmMatch(String txt, String pat) {
    int txtPointer;
    int patPointer;
    int txtLen = txt.length();  // txt의 문자 개수
    int patLen = pat.length();  // pat의 문자 개수
    int[] skip = new int[Character.MAX_VALUE + 1];  // 건너뛰기 표

    // 건너뛰기 표 만듦
    for (txtPointer = 0; txtPointer < Character.MAX_VALUE; txtPointer++)
        skip[txtPointer] = patLen;  //-- 일단 다 패턴 길이로 초기화
    for (txtPointer = 0; txtPointer < patLen - 1; txtPointer++)
        skip[pat.charAt(txtPointer)] = patLen - txtPointer - 1;
        
	//----------└→ 여기까지 하면, 『txtPointer == patLen - 1』
    // 검색
    while (txtPointer < txtLen) {
        patPointer = patLen - 1;    // pattern의 끝 문자에 주목

        while (txt.charAt(txtPointer) == pat.charAt(patPointer)) {
            if (patPointer == 0) 
                return txtPointer;  // 검색 성공
            txtPointer--;
            patPointer--;
        }
        txtPointer += (skip[txt.charAt(txtPointer)] > patLen - patPointer)
                ? skip[txt.charAt(txtPointer)] : patLen - patPointer;

    }
    return -1;  // 검색 실패
}