#include <iostream>
#include <cstdlib>
#include <cmath>
#include <string>

using namespace std;

int make_hash(string word, int word_length, int prime_number, int base, int offset);
int update_hash(int word_hash, int word_length, int base, int prime_number, int new_letter, int old_letter);

void Karpa_Rabin(string text, string word, int word_length, int text_length, int search_word_hash, int base, int prime_number, int offset);

int main()
{
    int word_hash = 0;
    int base = 0,prime_number = 101, word_length = 0, offset = 0, text_length = 0;
    string alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWYZ,:.?! ";
    string word;
    string text = "Ala ma kota? A : kot! a ma Ala.\n";
    cout << text << endl;
    cout << "podaj słowo:\n";
    cin >> word;
    base = alphabet.length();
    word_length = word.length();
    text_length = text.length();
    word_hash = make_hash(word, word_length, prime_number, base, offset);
    cout << "hash:" << word_hash << "\n";
    Karpa_Rabin(text, word, word_length, text_length, word_hash, base, prime_number, offset);


    return 0;
}
int make_hash(string word, int word_length, int prime_number,int base, int offset){
    int word_hash = 0;
    for(int i=0 ; i<word_length ; i++){
        word_hash += (word[i]-offset)*(pow(base,word_length-i-1));
        cout << "*" << word[i] << "*\n";
    }
    word_hash = word_hash%prime_number;
    return word_hash;
}
int update_hash(int word_hash, int word_length, int base, int prime_number, int new_letter, int old_letter){
    word_hash = (word_hash-(old_letter%prime_number)*(pow(base,word_length-1)%prime_number)%prime_number+prime_number)%prime_number;
    return word_hash;
}

void Karpa_Rabin(string text, string word, int word_length, int text_length,int search_word_hash, int base, int prime_number, int offset){
    int word_hash = 0, rolling_hash = 0;
    int old_letter = 0, new_letter = 0, i = 0;
    word_hash = make_hash(word, word_length, prime_number, base, offset);
    rolling_hash = make_hash(text, word_length, prime_number, base, offset);
    cout << rolling_hash << "**\n";
    while(i <= text_length-word_length){
        if(word_hash == rolling_hash)
            cout << "Zanaleziono slowo na pozycji: " << i << endl;
        if(i < text_length-word_length){
            old_letter = text[i] - offset;
            new_letter = text[word_length+text_length+1] - offset;
            rolling_hash = update_hash(rolling_hash, word_length, base, prime_number, old_letter, new_letter);
        }
    cout << rolling_hash << "\n";
    i++;
    }
}