Алгоритм соответствия строк Рабина Карпа

Ответ 1

О волшебных цифрах Пол отвечает довольно ясно.

Что касается кода, основная идея Рабина Карпа состоит в том, чтобы выполнить хеш-сравнение между скользящей частью строки и шаблоном.

Хэш не может быть вычислен каждый раз на всех подстроках, иначе сложность вычислений будет квадратичной O(n^2) вместо линейной O(n).

Следовательно, применяется функция roll hash, например, на каждой итерации требуется только один символ для обновления хэш-значения подстроки.

Итак, дайте комментарий вашему коду:

for (int i = 0; i < B.Length; i++)
{
    siga = (siga * D + (ulong)A[i]) % Q;
    sigb = (sigb * D + (ulong)B[i]) % Q;
}
if (siga == sigb)
{
    Console.WriteLine(string.Format(">>{0}<<{1}", A.Substring(0, B.Length), A.Substring(B.Length)));
    return;
}

^ Эта часть вычисляет хэш шаблона B (sigb) и хэш-код исходной подстроки A той же длины B. На самом деле это не совсем правильно, потому что хеш может столкнуться¹ и так, необходимо изменить оператор if: if (siga == sigb && A.Substring(0, B.Length) == B).

ulong pow = 1;
for (int k = 1; k <= B.Length - 1; k++)
    pow = (pow * D) % Q;

^ Здесь вычисляется pow, что необходимо для выполнения катящегося хеша.

for (int j = 1; j <= A.Length - B.Length; j++)
{
    siga = (siga + Q - pow * (ulong)A[j - 1] % Q) % Q;
    siga = (siga * D + (ulong)A[j + B.Length - 1]) % Q;
    if (siga == sigb)
    {
        if (A.Substring(j, B.Length) == B)
        {
            Console.WriteLine(string.Format("{0}>>{1}<<{2}", A.Substring(0, j),
                                                                A.Substring(j, B.Length),
                                                                A.Substring(j + B.Length)));
            return;
        }
    }
}

^ Наконец, оставшаяся строка (то есть от второго символа до конца) сканируется, обновляя хеш-значение подстроки A и сравнивая с хешем из B (вычисленным в начале).

Если два хэша равны, подстрока и шаблон сравниваются¹, и если они фактически равны, возвращается сообщение.

¹ Значения хеша могут столкнуться; следовательно, если две строки имеют разные значения хеширования, они определенно разные, но если эти два хэша равны, то они могут быть равными или нет.

Ответ 2

Алгоритм использует хэширование для быстрого сравнения строк. Q и D - магические числа, которые, по-видимому, кодер, возможно, достигнут с небольшим количеством проб и ошибок и дают хороший распространение хеш-значений для этого конкретного алгоритм.

Вы можете видеть эти типы магических чисел, используемых для хэширования многих мест. Ниже приведен пример декомпилированного определения функции GetHashCode типа строки .NET 2.0:

[ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
public override unsafe int GetHashCode()
{
    char* chrPointer = null;
    int num1;
    int num2;
    fixed (string str = (string)this)
    {
        num1 = 352654597;
        num2 = num1;
        int* numPointer = chrPointer;
        for (int i = this.Length; i > 0; i = i - 4)
        {
            num1 = (num1 << 5) + num1 + (num1 >> 27) ^ numPointer;
            if (i <= 2)
            {
                break;
            }
            num2 = (num2 << 5) + num2 + (num2 >> 27) ^ numPointer + (void*)4;
            numPointer = numPointer + (void*)8;
        }
    }
    return num1 + num2 * 1566083941;
}

Вот еще один пример из функции переопределения GetHashcode с R # для типа образца:

    public override int GetHashCode()
    {
        unchecked
        {
            int result = (SomeStrId != null ? SomeStrId.GetHashCode() : 0);
            result = (result*397) ^ (Desc != null ? Desc.GetHashCode() : 0);
            result = (result*397) ^ (AnotherId != null ? AnotherId.GetHashCode() : 0);
            return result;
        }
    }

Ответ 3

У меня проблема в объяснении функции каждой строки script может дать мне объяснение следующего script:

public static int[] RabinKarp(string A, string B)
    {
        List<int> retVal = new List<int>();
        ulong siga = 0;
        ulong sigb = 0;
        ulong Q = 100007;
        ulong D = 256;

        for (int i = 0; i < B.Length; ++i)
        {
            siga = (siga * D + (ulong)A[i]) % Q;
            sigb = (sigb * D + (ulong)B[i]) % Q;
        }

        if (siga == sigb)
            retVal.Add(0);

        ulong pow = 1;

        for (int k = 1; k <= B.Length - 1; ++k)
            pow = (pow * D) % Q;

        for (int j = 1; j <= A.Length - B.Length; ++j)
        {
            siga = (siga + Q - pow * (ulong)A[j - 1] % Q) % Q;
            siga = (siga * D + (ulong)A[j + B.Length - 1]) % Q;

            if (siga == sigb)
            if (A.Substring(j, B.Length) == B)
                retVal.Add(j);
        }

        return retVal.ToArray();
    }