Rabin-Karp 알고리즘
라빈-카프(Rabin-Karp) 알고리즘은 문자열 패턴을 수치로 해싱하고, 그 수치를 비교하여 같은 패턴인지 판단하는 방법이다.
위와 같이 문자열과 찾고자 하는 패턴이 주어지는 경우 라빈-카프 알고리즘을 사용하여 시간 복잡도를 줄일 수 있다. 문자열과 패턴에 사용되는 문자의 개수가 D개라고 하면, 문자열의 해시 값은 문자열을 D진수로 표현한 값이 된다. 예와 같이 사용 문자가 3개이고, 패턴의 길이가 3인 경우 3자리 3진수로 수치화 되는 것이다.
라빈-카프 알고리즘을 사용하지 않으면 문자열의 모든 부분에서 시작하는 부분 문자열이 패턴과 같은지 검사해야 하므로 O(N*l)의 시간이 걸린다. (N : 문자열 길이, l : 패턴 길이) 라빈-카프 알고리즘에서는 window를 한칸씩 옆으로 옮기며 문자열을 해싱하고, 이는 직전 window에서 계산한 값을 사용해 현재 window의 해시 값을 계산할 수 있게한다. 따라서 O(N)시간이 필요하다.
2차원 배열
문자열뿐만 아니라 2차원인 이미지에서도 특정 패턴을 수치화하여 매칭을 검사할 수 있다.
- 누적합을 사용하기
이미지의 값에 가중치를 곱해 누적합을 구한다. 그러면 이미지의 어떤 위치에서라도 패턴과 같은 가중치를 곱한 해시를 얻을 수 있게 된다. 위의 예시와 같이 패턴과 같은 크기의 누적합을 구한 뒤 왼쪽 위 가중치를 0으로 만들어주면 되기 때문이다. 이 방법을 사용하면 누적합을 계산한 뒤 이미지의 어떤 위치라도 상수 시간 내에 해시를 구할 수 있지만, 누적합을 사용하기 때문에 값이 커져 오버플로우를 조심해야 한다.
- 가로에 적용 후 세로에 적용하기
패턴의 가로 해시를 먼저 구한 뒤 그 해시를 사용하여 다시 최종 해시를 구하는 방식이다. 라빈-카프 알고리즘을 2번 적용하는 것과 같다. 라빈-카프 알고리즘을 사용하여 O(N*M) 시간에 가로 해시를 구하고, 다시 O(N*M) 시간에 최종 해시를 구할 수 있다. 따라서 O(2*N*M) 시간이 필요하다.
