라빈-카프 알고리즘
•
문자열 검색을 위해 해시 값 함수를 이용
•
패턴 내의 문자열을 일일이 비교하는 대신에 패턴의 해시 값과 본문 안에 있는 하위 문자열의 해시값만을 비교
•
최악의 시간 복잡도는 O(MN)이지만 평균적으로는 선형에 가까운 빠른 속도를 가지는 알고리즘
찾고자 하는 문자열에서 해쉬값을 구할 때
•
찾고자 하는 문자열에서 한글자씩 이동하며 패턴 길이만큼 읽어서 해쉬 값을 계산하는 것이 아니라
•
새로 추가되는 문자와 그 전에 읽었던 값을 이용하여 해쉬값을 구한다.
•
즉 아래 그림처럼 다음 해쉬값을 구할 때 그 전의 해쉬값을 이용한다.
고려사항
•
처음 해쉬 값을 구할 때는 찾고자 하는 문자열에서 패턴 길이 만큼 읽어서 구한다.
•
본 예제에서는 이해를 돕기 위해 패턴의 길이를 4자리 정수로 작게 했지만 패턴이 문자열이며 길이가 커지면 일정 자리수로 맞추기 위해 mod 연산을 취해준다(해쉬)
•
따라서 해쉬 값이 일치하더라도 실제 패턴이 일치하지 않을 수 있기 때문에 해쉬 값이 일치하면 문자열 일치를 검사해야 한다(해쉬 충돌)
보이어 무어 알고리즘
•
오른쪽에서 왼쪽으로 비교하는 알고리즘
•
보이어-무어 알고리즘은 패턴에 오른쪽 끝에 있는 문자가 불일치 하고 이 문자가 패턴 내에 존재하지 않는 경우, 이동 거리는 무려 패턴의 길이 만큼이 된다.
•
최악의 시간 복잡도는 O(MN)이지만 최선의 시간 복잡도는 O(N/M)이며 평균적으로는 가장 빠른 속도를 가지는 알고리즘
Case - 오른쪽 끝에 있는 문자가 불일치 하고 이 문자가 패턴 내에 존재하는 경우
•
실제로는 패턴의 포인터가 움직이는 것이 아닌 T[] 배열의 포인터가 이동하는 것!
skip 배열 만들기
•
skip[ ch ] : 본문 ch 문자에서 패턴 불일치가 발생했을 때 본문 포인터의 skip 횟수를 저장
•
패턴에 포함되지 않은 문자들은 본문 포인터가 패턴 길이만큼 skip 해야하므로 패턴의 길이가 곧 skip 배열의 값이 됨
•
패턴 문자들의 skip 배열 값(패턴 마지막 문자는 제외)
◦
(패턴 문자열의 길이 - 1) - 각 패턴 문자의 인덱스
◦
ex) rithm의 skip 배열
◦
만약 중복되는 문자 (ritthm 처럼)가 있으면 제일 뒤쪽 기준으로 맞춘다.
KMP(Knuth-Morris-Pratt) 알고리즘
•
불일치가 발생한 텍스트 문자열의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로, 불일치가 발생한 앞부분에 대하여 다시 비교하지 않고 매칭을 수행
•
보이어 무어 알고리즘과 다르게 원본 문자열이 아닌 패턴 문자열의 포인터를 바꿈!
•
패턴을 전처리하여 부분일치 테이블 배열 pi[k]을 구해서 잘못된 시작을 최소화함
◦
pi[k] : 처음부터 k 인덱스까지를 끝으로 하는 부분 문자열에서 일치하는 접두사와 접미사가 일치하는 최대 길이
•
시간 복잡도 : O(M+N)
KMP 동작
•
텍스트에서 abcdabc까지는 매치되고, e에서 실패한 상황
•
맨 앞의 abc와 실패 직전의 abc는 동일함을 이용할 수 있다.
•
실패한 텍스트 문자와 P[4]를 비교한다.
패턴을 이용한 부분일치 테이블 만들기
•
매칭이 실패했을 때 패턴 포인터가 돌아갈 곳을 계산
•
