RollingHash

RollingHash.cpp

#include "RollingHash.h"

RollingHash::RollingHash(const std::string& text, unsigned long wordLength) : text(text) {
    this->textLength = text.size();
    this->wordLength = wordLength;
    hash = 0;

    initHash();

    windowStart = 0;
    windowEnd = wordLength;
}

RollingHash::RollingHash(const std::string& word) : RollingHash(word, word.size()) {}

void RollingHash::initHash() {
    for (int i = 0; i < wordLength; i++) {
        int ch = text[i] - a + 1; // normalize from
        hash += mod(ch * powMod(nAlphabet, wordLength - i - 1));
    }
}

void RollingHash::move() {
    if (windowEnd > textLength - 1) return;

    int chOld = text[windowStart++] - a + 1;
    int chNew = text[windowEnd++] - a + 1;

    // remove the oldest char
    hash = hash - mod(chOld * powMod(nAlphabet, wordLength - 1));
    hash = mod(hash * nAlphabet);
    // add the newest one
    hash = mod(hash + chNew);
}


long long int RollingHash::mod(long long int num) {
    return (num % base + base) % base;
}

/**
 *
 * https://www.rookieslab.com/posts/fast-power-algorithm-exponentiation-by-squaring-cpp-python-implementation
 * */
long long int RollingHash::powMod(long long int num, unsigned long pow) {
    long long int result = 1;
    while (pow > 0) {
        if (pow & 1) {
            result = (result * num) % base;
        }
        pow >>= 1; // divide by 2
        num = num * num % base;
    }
    return result;
}

void RollingHash::operator++() {
    move();
}

bool RollingHash::operator==(const RollingHash& other) {
    return hash == other.hash;
}

RollingHash.h

#ifndef PROJECT5_ROLLINGHASH_H
#define PROJECT5_ROLLINGHASH_H


#include <string>

class RollingHash {
    const int a = 'a';
    const int nAlphabet = 26;
    const long base = 1000000007;

    std::string text;
    unsigned long wordLength;
    unsigned long textLength;
    unsigned long windowStart;
    unsigned long windowEnd;

    long long int mod(long long int num);

    long long int powMod(long long int num, unsigned long pow);

    void initHash();

public:
    long long int hash;

    void move();

    void operator++();

    bool operator==(const RollingHash& other);

    explicit RollingHash(const std::string& text, unsigned long wordLength);

    explicit RollingHash(const std::string& word);

};


#endif //PROJECT5_ROLLINGHASH_H