본문 바로가기

전체 글

 (736)
radix tree [1. 개요] [3. 코드]
라빈-카프 [3033] [1. 문제 설명]https://www.acmicpc.net/problem/3033[2. 풀이 접근]완전 탐색으로 접근부분 문자열이 발생할 수 있는 대상은 아래와 같다.부분 문자열의 길이는 1 부터 L-1 까지길이 L-1 부터 발생 할 수 있는 모든 부분 문자열을 모두 확인하여 비교하는 방법라빈-카프 알고리즘 등을 이용하여 문자열 비교를 진행하더라도, O(L2) 의 시간 복잡도 발생이분 탐색으로 접근길이가 4인 부분 문자열이 2개 이상 존재한다고 했을 때,길이가 3인 부분 문자열의 존재는 굳이 확인하지 않아도 된다."ABCDE"FGH"ABCDE"XYZ=> ABCD 라는 중복 되는 부분 문자열이 있음을 바로 알 수 있다.즉, 중복 되는 부분 문자열이 있을 때, 그 보다 작은 길이의 부분 문자열의 중복 존재..
라빈-카프 알고리즘 [1. 개요] [2. 해시 함수 구현]해시 충돌을 최대한 적게 발생 시키게 하기 위해 K 와 mod 값을 선택해야 하는데두 값 모두 소수 (prime number) 로 선택하는 편이 좋다고 한다.K: 31, 53, 101, 127, 131, 137, ...mod: 1e9+7 과 같은 큰 수. (1e9+3, 1e9+9)# 십만자리 : 1e5+3# 백만자리 : 1e6+3특히 K 는 문자열의 상황에 따라 다른데,알파벳 소문자로 구성 된 경우 : 31, 127, 131, ...알파벳 대소문자 + 숫자 로 구성된 경우 : 53, 131, 911, ...그 외, 257, 997, 1009최소 31 부터 소수 인 값을 선택하면 좋음특히, 거듭제곱 등의 연산이 발생하기 때문에 overflow 에 유의하도록 한다.

티스토리툴바