1. 브루트-포스법

---

• 검색할 문자열을 패턴, 문자열 원본을 텍스트라 명명함
• 단순법, 소박법이라고도 불림
• 첫번째 문자열부터 하나씩 비교해가며 일치하지 않을 시, 한칸 이동 후 반복
• 모든 경우의 수를 일일이 탐색하여 정답을 찾아내기 때문에 가장 비효율적

ex)

 public static int bMatch(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 { // 패턴 불일치시, 패턴 인덱스 초기화, 텍스트 인덱스 +1
                pt = pt - pp + 1;
                pp = 0;
            }
        }

        if(pp == pat.length()){ // 일치 시작하는 인덱스 return, 없으면 -1 return
            return pt - pp;
        }
        return -1;
    }

2. KMP법

---

• 검색 결과를 기억해 중간 검사 결과를 효율적으로 사용하는 알고리즘
• 브루트-포스법보다 복잡하고 보이어-무어법과는 성능이 같거나 좋지않아 실제로는 거의 사용하지 않는다.

한칸씩 이동하는 브루트-포스보다 패턴을 최소의 횟수로 옮겨 효율적이다.
이동시킬 때마다 계산하는건 비효율적이니 ‘몇 번째 문자부터 다시 검색할지’에 대한 표를 미리 만들어놔야 한다.

2.1 패턴 표 만들기

• 패턴 2개를 겹쳐 1번째 문자가 다른 경우 아래 패턴을 1칸 뒤로 옮기고 1번째 문자부터 다시 검사합니다.
  

3. 보이어-무어법

---

• 가장 효율적이라 실제로 많이 쓰이는 알고리즘
• 패턴의 마지막 문자부터 앞쪽으로 거꾸로 검사 진행
• 텍스트마다 몇칸을 옮겨야할지 미리 정해놔 옮기며 진행

이렇듯 KMP처럼 패턴의 중복된 문자의 건너뛰기 표를 만드는 것이 아닌
모든 문자열에 대해 몇칸 이동해야하는지 표를 작성해 비교하며 이동

1. 패턴에 들어있지 않은 문자를 만난 경우 - 패턴을 옮길 크기는 패턴 사이즈만큼 옮기면 됩니다.
2. 패턴에 들어있는 문자를 만난 경우 - 마지막에 나오는 위치의 인덱스가 K면 패턴을 옮길 크기는 N – K – 1

---

참고 도서

• Do it! 자바 프로그래밍 입문