문자열매칭1 chapter10 문자열탐색 10.1 문자열 탐색 알고리즘의 개요Ctrl+F : 탐색단축키본문 : 탐색 대상 문자열패턴 : 탐색어이동 : 탐색 위치 옮기기10.2 고지식한 탐색 알고리즘본문 길이가 n이고 패턴 길이가 k이면 인덱스 0~n-k까지 패턴단위로 한 칸 한 칸 옮겨서 탐색 해보는 것최악의 경우 NxM번의 비교 수행10.3 카프-라빈 알고리즘알고리즘의 핵심 : 해싱 10.3.1 카프-라빈 알고리즘의 동작 방식문자열 탐색을 위해 해시 함수를 이용한다. 패턴의 해시값과 본문 내의 하위 문자열의 해시값을 비교하는 방식연산 비용은 더 커보이는데 천재적인 영감은? 해시함수의 비용을 획기적으로 줄이는 방법 패턴의 길이 m = 4 본문 = S[0…3]인 해시값 H = S[0]x2^3 + S[1]x2^2 + S[2]x2^1 + S[3]x2.. 2023. 6. 9. 이전 1 다음