karp

라빈-카프 알고리즘 (Rabin-Karp) 해시값을 통한 문자열 비교

정의 / 시간 복잡도 O(n) 문자열에 해싱 기법을 사용하여 해시 값으로 비교하는 알고리즘이다. 간단하게 해시 값을 만들려면 문자열의 각 문자(ASCII TABLE 값)에 특정 수의 제곱 수를 차례대로 곱하여 모두 더하면 된다. 이러한 방식을 사용하면 두 문자열이 서로 다를 때 두 문자열의 해시 값이 다르게 나오게 된다. 예를 들어 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 이므로 ABCD와 ABED 두 문자열은 서로 일치하지 않는다는 결과가 된다. 간혹 해시 값이 서로 충돌하는 해시 충돌 ..