[자바 Do It! 알고리즘]Chapter07 문자열 검색 (KMP법)

[KMP 법]

1. KMP법은 브루스-포스법과 달리, 검사했던 위치 결과를 버리지 않고 이를 효율적으로 활용하는 알고리즘입니다.

2. 텍스트와 패턴의 겹치는 부분을 찾아내어 검사를 다시 시작할 위치를 구합니다. 이런 방법으로 패턴을 최소의

횟수로 옮겨 알고리즘의 효율을 높입니다.

3. 하지만 몇 번째 문자부터 다시 검색을 시작할 지 패턴을 이동시킬 때 마다 다시 계산해야 한다면 높은 효율을

기대할 수 없습니다. 그래서 '몇 번째 문자부터 다시 검색할지'에 대한 값을 미리 '표'로 만들어 이 문제를

해결합니다.

1) 표를 작성할 때는 패턴 안에서 중복되는 문자의 나열을 먼저 찾아야 합니다. 이 과정에서 KMP 법을 사용합니다.

2) 패턴 안에서 중복되는 문자의 나열을 찾기 위해 패턴끼리 겹쳐놓고 생각해 보겠습니다. 패턴의 1번째 문자가 서로

다른 경우 아래의 패턴을 1칸 뒤로 옮기고 1번째 문자부터 다시 검사합니다.