728x90 반응형 Rabin-Karp1 rabin-karp 이번에는 hashing을 활용한 문자열 매칭 알고리즘인 라빈-카프(rabin-karp)에 대해 알아보고자 합니다. 라빈-카프 알고리즘의 시간복잡도는 O(N)으로 지금까지 진행하였던 왠만한 문자열 매칭 알고리즘보다 빠르다는 장점이 있습니다.그치만, 여러 가지 다양한 부분에서 문제점이 있어 실제 서비스에서는 사용하기 어렵다는 단점이 있습니다. 장점 - 시간이 빠르다단점 - hashing 값이 충돌이 날 수 있다. - overflow가 발생할 수 있다. "abbaba"라는 문자열에 "aba"라는 문자가 포함되어 있는지 확인하는 방법을 예시로 들어보겠습니다.hashing을 사용하기 때문에, 자리수마다의 문자의 아스키 코드 넘버에 특정 값을 곱하여 하나의 숫자 단위로 표현합니다.2를 활용하여 예시를 들면 pat.. 2024. 7. 11. 이전 1 다음 728x90 반응형