Реализация алгоритма Рабина-Карпа на C++

Приветствую вас, друзья мои! Сейчас я расскажу о своей первой курсовой работе, которая была написана и сдана на далеком втором курсе. Суть заключается в реализации и тестировании алгоритма Рабина-Карпа поиска подстроки в строке, в качестве языка программирования мне был рекомендован C++. В принципе больше во вступлении добавить нечего, перейдем сразу к делу.

Суть алгоритма Рабина-Карпа

Алгоритм представляет из себя улучшенную версию последовательного поиска, улучшение заключается в использовании хэш-функции. Это объясняется тем, что сравнить два числа(два хэша) гораздо быстрее и дешевле, чем сравнивать подстроки посимвольно. Сравнивать подстроки придется только один раз, когда хэши совпали, сделать это придется для увеличения надежности и защиты от случая коллизии хэша.

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

Формула хэша подстроки

H = C₁h^k-1 + C₂h^k-2 + … + C_kh⁰

где C₁… C_kвходные символы, h константа. Удаление символов из подстроки и добавление новых производится путем вычитания последнего члена формулы и добавлением первого соответственно.

Конечно, можно использовать любой другой хэш, не обязательно кольцевой. Кроме того, именно сравнение скорости работы при разных хэш-функциях и было целью моей курсовой. Я пробовал adler32 и функцию Дженкинса, обе показали гораздо более медленный результат, чем кольцевая функция.

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

Реализация кольцевой хэш-функции на C++

Функция на вход принимает строку для подсчета хэша, ее длину, предыдущий хэш, указатель на константу h. Указатель потому, что она должны быть общей для многих вызовов функции, я решил не делать ее глобальной, а просто завести выше по стеку и работать с ней по указателю.

В начале проверяем, если константа не инициализирована, то высчитываем ее функцией hInit(). Далее идет проверка, что это первый хэш, тогда просто высчитываем его по формуле, иначе, согласно правилу пересчета, вычитаем первый элемент строки и добавляем последний. Возвращается новый хэш от строки.

int hInit(unsigned int strLen) {
    int d = 52;
    int    p = 65713;

    int h = 1;
    for(unsigned int i=1; i < strLen; i++) {
        h = (h*d) % p;
    }

    return h;
}

int ringHash(char* str, unsigned int strLen, int prevHash, int *h) {
    int d = 52; //Константа из формулы
    int    p = 65713; //Вычисления производятся по модулю простого числа

    //h = d^(len-1) (mod p) - константа для быстроого пересчета хэша
    if(*h == 0) { //Если константа не инициализирована
        *h = hInit(strLen);
    }

    //Если считаем хеш первый раз
    if(prevHash == 0) {
        for(unsigned int i=0; i<strLen; i++) {
            prevHash += (d*prevHash + (int)str[i]) % p;
        }
        if(prevHash < 0) {
            prevHash += p;
        }

        return prevHash;
    }
    //Если пересчитываем для другого окна
    else {
        int hash = (d * (prevHash - (int)str[0] * (*h)) + (int)str[strLen]) % p;
        if(hash < 0) {
            hash += p;
        }

        return hash;
    }
}