핵심
라빈-카프 알고리즘 (Rabin-Karp)
NOTE
라빈-카프알고리즘은 문자열에 해싱 기법을 사용하여 해시 값으로 비교하는 알고리즘이다
•
간단하게 해시 값을 만들려면 각 문자에 특정 수의 제곱 수를 차례대로 곱하여 더하면 됨
◦
ex) ABCD와 ABED
▪
ABCD의 해시 값은 65 * 3^3 + 66 * 3^2 + 67 * 3^1 + 68 * 3^0 = 2618
▪
ABED의 해시 값은 65 * 3^3 + 66 * 3^2 + 69 * 3^1 + 68 * 3^0 = 2624
알고리즘 원리
NOTE
•
문자열 AABDCDABD에서 패턴 ABD가 발견되는 지 라빈-카프 알고리즘을 통해 탐색
•
폐수 - 본인 건물 거리