문자열 탐색 - 카프 라빈

카프라빈 알고리즘은

찾고 싶은 문자열과 비교할 타깃 문자열을 해쉬 하여 비교하는 알고리즘이다.

같은 문자를 해쉬하면 같은 값이 나오는 원리를 이용한 것이다.

여기서 중요한 것은 해쉬를 하면 연산이 늘어나서 

결국 고지식한 알고리즘과 다를 게 없지 않을까 했는데 그렇지 않다.

그 이유는 카프 라빈은 천재이고, 이 사람들은 해쉬 연산을 최적화하여 속도를 더 올렸다고 한다.

그 방법은 타겟 문자열을 해쉬해 나갈 때, 첫 문자와 마지막 문자만 변하는 형식일 것이다.

여기서 중복되는 가운데 문자열의 해쉬 연산을 줄여서 속도를 올린다.

이러한 해쉬시 알고리즘을 롤링 해시라고 한다.

원리는 기존의 문자열을 패턴길이만큼 해시하여 비교할 때,

다음 해시해야하는 문자열이 이전의 해시값으로 나타내진다. 

사실상 롤링 해시를 통해 해시를 해두면 뒤의 비교할 문자열들은 해시를 할 필요가 없다.

여기서 중요한 점은 해시이기 때문에 충돌이 일어날 수 있고 이를 피하기 위한 적절한 값을 찾아야 한다는 숙제 또한 피할 수 없다.

 

int KarpRabin(char* Text, int TextSize, int Start, char* Pattern, int PatternSize)
{
    int i = 0;
    int j = 0;
    int Coefficient = pow(2, PatternSize - 1);

    int HashText = Hash(Text, PatternSize);
    int HashPattern = Hash(Pattern, PatternSize);

    for (i = Start; i <= TextSize - PatternSize; i++)
    {
        HashText = ReHash(Text, i, PatternSize - 1, HashText, Coefficient);
        //std::cout << HashPattern << " = " << HashText << "\n";
        if (HashPattern == HashText)
        {
            for (j = 0; j < PatternSize; j++)
            {
                if (Text[i + j] != Pattern[j])
                    break;
            }

            if (j >= PatternSize)
                return i;
        }
    }

    return -1;
}

int Hash(char* String, int Size)
{
    int i = 0;
    int HashValue = 0;

    for (i = 0; i < Size; i++)
    {
        HashValue = String[i] + (HashValue * 2);
    }

    return HashValue;
}

int ReHash(char* String, int Start, int Size, int HashPrev, int Coefficient)
{
    if (Start == 0)
        return HashPrev;

    return String[Start + Size - 1] +
        ((HashPrev - Coefficient * String[Start - 1]) * 2);
}