Rabin-Karp를 사용하여 문자열에서 여러 패턴을 검색합니다.

Question

에 따르면 Wikipedia 항목 Rabin-Karp String 일치 알고리즘에서는 선형 복잡성을 유지하면서도 동시에 문자열에서 여러 다른 패턴을 찾는 데 사용할 수 있습니다. 모든 패턴이 같은 길이 일 때 쉽게 이루어질 수 있지만 길이가 다른 패턴을 동시에 검색 할 때 O (n) 복잡성을 보존 할 수있는 방법을 여전히 알지 못합니다. 누군가 이것에 대해 약간의 빛을 비추어 줄 수 있습니까?

편집 (2011 년 12 월) :

Wikipedia 기사는 그 이후로 업데이트되었으며 더 이상 O (n)의 여러 길이의 여러 패턴과 일치한다고 주장하지 않습니다.

Answer 1

이것이 정답인지 확실하지 않지만 어쨌든 :

구성하는 동안 해시 값, 우리는 문자열 해시 세트에서 일치를 확인할 수 있습니다. 일명, 현재의 해시 가치. 해시 함수/코드는 일반적으로 루프로 구현되며 해당 루프 내부에서는 빠른 검색을 삽입 할 수 있습니다.

물론 우리는 선택해야합니다 m 문자열 세트에서 최대 문자열 길이를 갖습니다.

업데이트: Wikipedia에서

[...]
for i from 1 to n-m+1
         if hs ∈ hsubs
             if s[i..i+m-1] = a substring with hash hs
                 return i
         hs := hash(s[i+1..i+m]) // <---- calculating current hash
[...]

우리는 계산합니다 현재의 해시 m 단계. 각 단계마다 a 일시적인 해시 세트에서 찾을 수있는 해시 값 (O (1) 복잡성). 모든 해시는 크기와 같은 크기, 즉 32 비트를 갖습니다.

Update 2: 상각 된 (평균) O (N) 시간 복잡성?

위의 나는 그렇게 말했다 m 최대 문자열 길이가 있어야합니다. 우리는 반대를 이용할 수 있다는 것이 밝혀졌습니다.
와 함께 서브 스트링 검색을 이동하기위한 해싱 그리고 고정 m 크기 우리는 o (n) 복잡성을 달성 할 수 있습니다.

가변 길이 문자열이 있으면 설정할 수 있습니다 m 최소 문자열 길이로. 또한 해시 세트에서 해시를 전체 문자열과 연관시키지 않고 첫 번째 M- 문자와 연결합니다.
이제 텍스트를 검색하는 동안 현재 해시가 해시 세트에 있는지 확인하고 관련 문자열이 일치하는 것을 검사합니다.

이 기술은 잘못된 경보를 증가시킬 것이지만 평균적으로 O (n) 시간 복잡성이 있습니다.

Answer 2

하위 문자열의 해시 값이 수학적으로 관련되어 있기 때문입니다. 해시 계산 H (S, J) (문자열의 Jth 위치에서 시작하는 캐릭터의 해시 에스) 테이크 o (m) 길이의 시간에 시간 중. 그러나 일단 당신이 그것을 가지고 있으면 컴퓨팅 H (S, J+1) 일정한 시간에 수행 할 수 있습니다 H (S, J+1) 의 함수로 표현 될 수 있습니다 H (S, J).

o (m) + o (1) => o (m), 즉 선형 시간.

여기 링크가 있습니다 이것이 더 자세히 설명되는 곳 (예 : "Rabin-Karp를 빠르게 만드는 것은 무엇입니까?")를 참조하십시오.