Молодогвардейцев 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 для работы с огромными текстовыми файлами, писал тесты для разных хэш-функций и многое другое, что не стал вносить в статью, а оставил только саму реализацию Рабина-Карпа. У меня все, спасибо за внимание!

  • Александр

    Здравствуйте, хотелось бы узнать, как будет выглядеть главная функция main(), как осуществить ввод текста через консоль и вывод подстроки на консоли?

    • Полет фантазии практически неограничен, но есть например вот такой вариант. Рабин-Карп ищет индекс первого вхождения подстроки в тексте.
      int main(int argc, char** argv) {
      char text[255];
      char string[255];

      cout << "Enter text: " << endl;
      gets(text);

      cout << "Enter string: " << endl;
      gets(string);

      cout << rabinKarpSearch(text, string) << endl;

      return 0;
      }

      • Александр

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

        • Например, можно вместо return k; выводить их на консоль, записывать в файл и делать что душе угодно

        • Либо другой вариант: сделать возвращаемым значением vector, а на месте где return k; сделать push_back(k), в результате будет возвращен вектор индексов вхождений подстрок

  • Александр

    Доброго времени суток, такой вопрос, в 27 строчке в кольцевой хэш-функции есть условие, if(prevHash < 0) {
    prevHash += p;
    }
    зачем нужно это условие, что оно проверяет, и можно ли без него обойтись?

    • Для того, чтобы значение Хэша не было отрицательным. Отрицательным оно сможет стать, если после цикла получим переполнение инта

  • Александр

    Интересует вот еще что, почему в функции реализации алгоритма Р-К, в цикле k<=(textLen-strLen), ведь сказано пробегаем по тексту, длина которого у нас textLen, почему отнимает strLen? Пробовал не отнимать strLen, ответ(индекс) выводился верный, но у меня были маленькие предложения, может быть если я ввиду большой текст я почувствую отсутствие (-strLen). Надеюсь, вопрос понятен. Заранее спасибо.

    • Вы его действительно не почувствовали, потому что просто не дошли до конца. Отнимать strLen необходимо потому что мы бежим по тексту «окнами» размера strLen, следовательно последнее окно будет начинаться с индекса textLen-strLen

  • Александр

    Добрый день, такой вопрос, почему в hInit() d равно именно 52, может ли оно быть другим, и на что влияет значение d.

    • Если взглянуть на формулу кольцевого хэша на вики, то можно увидеть константу a, это она и есть. От качества ее подбора зависит качества хэша

      • Александр

        Как происходит этот подбор, от чего мне отталкиваться, когда я буду инициализировать d.
        Вы не ответили, почему именно 52 у вас. Заранее благодарен!