#include 
#include 
using namespace std;
typedef long long ll;
class String {
    char *chars;
    unsigned int length;

public:
    String() : chars(nullptr), length(0) {}

    ~String() {
        delete[] chars;
    }

    // Copy constructor
    String(const String& other) : length(other.length) {
        chars = new char[length + 1];
        for (unsigned int i = 0; i < length; i++) {
            chars[i] = other.chars[i];
        }
        chars[length] = '\0';
    }

    
    String& operator=(const String& other) {
        if (this != &other) {
            delete[] chars;
            length = other.length;
            chars = new char[length + 1];
            for (unsigned int i = 0; i < length; i++) {
                chars[i] = other.chars[i];
            }
            chars[length] = '\0';
        }
        return *this;
    }

    // setiranje na vrednostite
    void setString(const char* str) {
        length = 0;
        while (str[length] != '\0') length++;  // dolzinata da se najde
        
        chars = new char[length + 1];
        for (unsigned int i = 0; i < length; i++) {
            chars[i] = str[i];
        }
        chars[length] = '\0';
    }
    char getChar(unsigned int i) const {
        if(i < length) {
            return chars[i];
        }
        return '\0';
    }
    unsigned int getLength() const {
        return length;
    }
    
  
};


void rabin_carp(const String & text, const String & pattern, ll base, ll MOD) {
    unsigned int text_length = text.getLength();
    unsigned int pattern_length = pattern.getLength();
    
    unsigned int n = text.getLength();
    unsigned int window_size = pattern.getLength();
    
    ll pattern_hash = 0, sum = 0;
    for(unsigned int i = 0; i < window_size; i++) {
        pattern_hash = (pattern_hash * base + (ll) pattern.getChar(i)) % MOD;
        sum += (ll) pattern.getChar(i);
    }
    vector power(n + 1, 1);
    
    for(unsigned i = 1; i <= n; i++) {
        power[i] = (power[i - 1] * base) % MOD;
    }
    
    ll current_hash = 0, pref_sum = 0;
    for(unsigned int i = 0; i < window_size; i++) {
        current_hash = (current_hash * base + (ll) text.getChar(i)) % MOD;
        pref_sum += (ll) text.getChar(i);
    }
    
    if(sum == pref_sum and current_hash == pattern_hash) {
        bool ok = true;
        for(unsigned int i = 0; i < window_size; i++) {
            if(text.getChar(i) != pattern.getChar(i)) {
                ok = false;
                break;
            }
        }
        if(ok) {
            cout << "Matching at: " << 0 << endl;
        }
    }
    for(unsigned int i = 1; i <= n - window_size; i++) {
        
        current_hash = (current_hash - power[window_size - 1] * (ll) text.getChar(i - 1)) % MOD;
        
        current_hash = (current_hash * base + text.getChar(i + window_size - 1)) % MOD;
        pref_sum -= (ll) text.getChar(i - 1);
        pref_sum += (ll) text.getChar(i + window_size - 1);
        if(pref_sum == sum and current_hash == pattern_hash) {
            bool ok = true;
            for(unsigned int j = i; j < i + window_size; j++) {
                if(text.getChar(j) != pattern.getChar(j - i)) {
                    ok = false;
                }
            }
            if(ok) {
                cout << "Matching at: " << i << endl;
            }
        }
        
    }
}

int main() {
    String text;
    text.setString("ABBCAABCBB");
    
    String pattern;
    pattern.setString("BC");
    
    ll MOD = 1e9 + 7;
    rabin_carp(text, pattern, 26, MOD);
    
}