Молодогвардейцев 454015 Россия, Челябинская область, город Челябинск 89085842764
MindHalls logo

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

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

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

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

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

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

H = C1­­hk-1 + C2hk-2 + … + Ckh0

где C1 … Ck входные символы, 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;
    }
}

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

На вход принимает текст и строку, которую нужно найти в тексте. Кроме всего прочего, здесь я объявляю константу для быстрого пересчета хэша и отдаю указатель на нее в кольцевую функцию. Бежим по тексту, высчитываем хэш очередного «окна», сравниваем его с хэшом строки, если совпали, пробегаемся посимвольно и отдаем индекс вхождения подстроки.

int rabinKarpSearch(char* text, char* str) {
        unsigned int strLen = strlen(str);
        unsigned int textLen = strlen(text);
        int h = 0;

        //Хэш подстроки для поиска
        int strHash = ringHash(str, strLen, 0, &h);
        //Хэш первого окна в тексте
        int textHash = ringHash(text, strLen, 0, &h);

        for(unsigned int k = 0; k <= (textLen-strLen); k++) {
            if(strHash == textHash) {
                //Если хэши совпали, проверяем посимвольно
                for(unsigned int i = 0; (i < strLen) && (str[i] == text[k+i]); i++) {
                    if(i == (strLen-1)) {
                        return k;
                    }
                }
            }

            //Хэш следующего окна
            textHash = ringHash(&text[k], strLen, textHash, &h);
        }

        //Строка не найдена
        return -1;
}

Заключение

Вот такая нехитрая реализация получилась. Скажу честно, на втором курсе я знатно попотел во время разработки. Тем более, что я использовал WinAPI для работы с огромными текстовыми файлами, писал тесты для разных хэш-функций и многое другое, что не стал вносить в статью, а оставил только саму реализацию Рабина-Карпа. У меня все, спасибо за внимание!