라빈-카프(Rabin-Karp) 문자열 검색 알고리즘은 문자열에서 패턴을 찾는 알고리즘이다. 이 알고리즘은 해싱(hashing)을 사용하여 문자열을 검색하므로, 문자열의 길이에 비례하는 시간 복잡도를 갖는다.

라빈-카프 알고리즘은 다음과 같은 과정으로 동작한다.

1. 패턴 문자열의 해시값을 계산한다.
2. 검색 대상 문자열에서 패턴의 길이만큼 문자열을 잘라내어 해시값을 계산한다.
3. 패턴 문자열의 해시값과 잘라낸 문자열의 해시값이 일치하는지 확인한다.
4. 해시값이 일치하면, 잘라낸 문자열과 패턴 문자열을 비교하여 정확히 일치하는지 확인한다.
5. 일치하지 않으면, 검색 대상 문자열을 한 칸씩 이동하여 2번 과정부터 다시 시작한다.

이러한 과정을 반복하여 검색 대상 문자열에서 패턴과 일치하는 부분을 찾을 수 있다.

패턴 문자의 해시값 계산은 다음과 같다.

문자열의 길이를 n, 각 문자의 아스키 코드값을 a라고 할 때

$2^n*a+2^{n-1}*a … + 2^0 + a$

예를 들어, 'abbcaabb'의 해시값은 다음과 같이 계산된다.

97 * 2^7 +

98 * 2^6 +

97 * 2^5 +

99 * 2^4 +

97 * 2^3 +

97 * 2^2 +

98 * 2^1 +

98 * 2^0