rabin-carp 썸네일형 리스트형 Rabin-Karp String Matching Algorithm, 라빈-카프 알고리즘 https://www.youtube.com/watch?v=qQ8vS2btsxI 이 영상을 참고했다! 라빈-카프 알고리즘은 String을 비교하여 긴 문자열에 짧은 문자열이 포함되어 있는지 확인하는 알고리즘이다. brute force 방법으로, 문자열을 한칸씩 이동하며 모두 비교하는 방법부터 보이어-무어, KMP등 여러가지 방법을 공부했다. 라빈-카프의 핵심은, Hash function이다. 각 문자열의 값을 이렇게 할당한다고 했을 때, 'AAA' 의 값을 1 + 1 + 1 = 3으로 정의한다. 이렇게 해당 문자열의 값을 return해주는 함수가 hash 함수이다. (예시는 단순한 해시함수이다!) 'AAAAAAB' 안에 'AAB'가 존재하는지 확인하기 위해서, 'AAB'를 hash 함수에 넣고, 4라는 값.. 더보기 이전 1 다음
