초코레

브루트-포스법을 개선한 KMP법보다 효율이 더 우수하기 때문에 실제로 문자열 검색에 널리 사용되는 알고리즘 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정한다. 패턴에 존재할 수 있는 모든 문자의 옮길 크기를 계산하고 저장해야 하기 때문에 건너뛰기 표의 요소 개수는 Character.MAX_VALUE + 1 이다. Character.MAX_VALUE는 Char형으로 나타낼 수 있는 문자 수 패턴의 문자열의 길이가 n일 때 옮길 크기는 다음과 같다. 패턴에 들어 있지 않은 문자를 만난 경우 패턴을 옮길 크기는 n 이다. (현재 검사하고 있는 텍스트의 문자 위치로부터 다음에 검사할 패턴의 마지막 문자 위치가 n만큼 떨어질 수 있도록..

브루트-포스법을 개선한 알고리즘으로 검사했던 위치 결과를 버리지 않고 이를 효율적으로 활용하는 알고리즘 텍스트와 패턴의 겹치는 부분을 찾아내어 검사를 다시 시작할 위치를 구함으로써 패턴을 최소의 횟수로 옮겨 알고리즘의 효율을 높인다. 몇 번째 문자부터 다시 검색할지에 대한 값을 미리 표로 만들어 둔다. 건너뛰기 표를 작성할 때는 패턴 안에서 중복되는 문자의 나열을 먼저 찾아나기 위해 패턴끼리 겹쳐놓고 생각하여 만든다. KMP법은 브루트-포스법보다는 복잡하고 Boyer-Moore법과는 성능이 같거나 좋지 않기 때문에 실제 프로그램에서는 거의 사용되지 않는다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31..

문자열 검색의 기초 알고리즘 브루트-포스법은 선형 검색을 확장한 알고리즘으로 단순법, 소박법이라고도 한다. 이미 검사를 진행한 위치를 기억하지 못하므로 효율은 좋지 않다. 다른 문자를 만나면 패턴에서 문자를 검사했던 위치 결과를 버리고 다음 텍스트의 위치로 1칸 이동한 다음 다시 패턴의 첫 번째 문자부터 검사한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 //브루트-포스법으로 문자열을 검색 //여러 개라면 가장 앞쪽에 있는 인덱스 반환 static int bfMatch(String txt, String pat) { int pt = 0; //텍스..