브루트-포스법 / KMP법/ Boyer-Moore법

1. 브루트-포스법(brute force method)

텍스트 "ABACDEFGHA"에서 패턴 "ABC"를 브루트-포스법을 사용해 검색할수 있습니다.

브루트-포스법은 선형 검색을 확장한 알고리즘이므로 단순법, 소박법이라고도 부릅니다.

- 코드

String.indexOf 메서드로 이용이 가능합니다.

https://docs.oracle.com/javase/8/docs/api/java/lang/String.html

Modifier and Type	Method and Description
int	lastIndexOf(int ch) Returns the index within this string of the last occurrence of the specified character.
int	lastIndexOf(int ch, int fromIndex) Returns the index within this string of the last occurrence of the specified character, searching backward starting at the specified index.
int	lastIndexOf(String str) Returns the index within this string of the last occurrence of the specified substring.
int	lastIndexOf(String str, int fromIndex) Returns the index within this string of the last occurrence of the specified substring, searching backward starting at the specified index.

---

2. KMP

브루토 포스법은 다른 문자를 만나면 패턴에서 문자를 검사했던 위치결과를 버리고 다음 텍스트의 위치로 1칸 이동한 다음 다시 패턴의 첫 번째 문자부터 검사하므로 비효율적입니다. 그러므로 검사했던 위치를 결과를 버리지않고 이를 효율적으로 활용하는 알고리즘입니다.

- 패턴 이동 테이블 만들기

 1) 1번째는 B를 걸릴시 1칸이동후 0인덱스부터 검사하라는 뜻입니다.

 2) 3번째는 A는 1, B는 2라고 표시되어있습니다.

이뜻은 해당되는 패턴으로 이동시 A문자 패스하고 다음문자인 인덱스 1부터 검사하라는 뜻입니다.

하지만 해당 인덱스 1은 B입니다.

B 또한 패스하고 다음 인덱스인 2부터 검사하라는 뜻입니다.

3. Boyer-Moore법 (보이어무어법)

R.S Boyer와 J.S Moore가 만든 Boyer-Moore법은 KMP법보다 효율이 더 좋습니다. 이 알고리즘은 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정합니다.

- 코드

---

읽어보면 더 좋은 자료 : https://xenostudy.tistory.com/72