c++ 문자열 검색 O(N)으로 하기 with Rabin-Karp 알고리즘

문자열이 만약에 "dabcabkabcabd"라고 하자.

이 문자열 안에 "abcabd"라는 문자가 있는지 확인해보고자 한다.

 

만약 brute force로 검색한다면 복잡도는 O(N * M)이 될 것이다.

 

이것을 O(N + M)~~ O(N)으로 할 수가 있다.

사실 문자열 검색의 복잡도는 O(N)으로 끝내야 한다.

 

만약 두 문자열이 같다면 그 해쉬 값도 같다고 볼 수 있다.

 

슬라이딩 윈도우를 하면서, hash값만 비교하고(복잡도 O(N))

hash 값이 일치한다면 일치하는 hash값끼리만 문자열을 일일히 비교해보면 된다(복잡도 O(M))

 

코드 >>

#include <iostream>
#include <string>
 
// C++ Rabin-Kaap 알고리즘 쉽게 구현
 
 
int main()
{
    std::string find = "abcabd"; // Hash 값 : 12449668180088197040
    std::string b = "abcabd"; // Hash 값 : 12449668180088197040
    std::string total = "dabcabkabcabd"; // Hash 값 : 7653540513724806762
    
    std::hash<std::string> str_hash;
    
    // 같은 string이면 hash value가 같다.
    std::cout << "hash value of abcabd : " << str_hash(find) << std::endl;
    std::cout << "hash value of abcabd : " << str_hash(b) << std::endl;
    std::cout << "hash value of dabcabkabcabd : " << str_hash(total) << std::endl;
    size_t Findsize = find.size();
    size_t Totalsize = total.size();
 
;
    for (size_t i = 0; i <= Totalsize - Findsize; i++)
    {
        std::string tempString = total.substr(i, Findsize);
        // 해쉬값을 비교하므로 O(N) 가능
        if ( str_hash(tempString) == str_hash(find))
        {
            // 해쉬 충돌이 일어날 수 있으므로 일일히 문자열을 비교해 본다.
            // 그렇다면 시간 복잡도는 O(N+M) --> O(N)
            if (tempString == find)
            {
                std::cout << "검색어를 찾았습니다. 정답은 : " << tempString << std::endl;
            }
        }
    }
    return 0;
}