alg. Karpa-Rabina update hasha z modulo

Question

Dzień dobry,

udało mi się napisać algorytm Karpa-Rabina, lecz niestety nie ma jeszcze pełnej wydajności. Za pomocą metody Hornera, która działa w odwrotnym kierunku (najwyższa wielokrotność podstawy jest po prawej stronie, stąd poruszanie się po tablicy od prawej do lewej), z zastosowanym wyznaczaniem reszty z dzielenia mogę obliczyć hash, ale nie potrafię go zmodyfikować. Dokładnie to nie wiem, w jaki sposób odjąć wartość znaku po lewej, jak domnożyć hash i dodać po prawej nowy znak, czyli po prostu przesunąć hash o jedną pozycję w prawo. Dlatego póki co obliczam go ponownie za pomocą funkcji hasz.

Gdyby nie było modulo, po prostu odjąłbym wartość pierwszego znaku (bo podstawa^0), podzielił hash przez podstawę i na koniec dodał do niego wartość znaku przemnożonego przez podstawę podniesioną do potęgi <dł.wzorca-1>.

Bardzo proszę o pomoc.

 

#include <iostream>
#include <math.h>
using namespace std;

void indexview(string t);
unsigned short hasz(string t, unsigned i, unsigned l);
void kr(string t, string p);
unsigned short intlength(int i);

int main()
{
    string text, pattern;

    cout << "Wpisz tekst: ";
    getline(cin, text);
    cout << "Wpisz wzorzec: ";
    getline(cin, pattern);
    indexview(text);
    cout << endl;
    kr(text, pattern);

    return 0;
}

void indexview(string t)
{
    unsigned tl=t.size(), i=0, j;
    for (; i<tl; i++) cout << i <<  " ";
    cout << endl << t[0];
    for (i=1; i<tl; i++)
    {
        for (j=0; j<intlength(i); j++) cout << " ";
        cout << t[i];
    }
}

unsigned short intlength(int i)
{
    unsigned short x=0;
    if (i<0) x++;
    do
    {
        i/=10;
        x++;
    } while (i!=0);
    return x;
}

unsigned short hasz(string t, unsigned i, unsigned l)
{
    unsigned j=l-1;
    unsigned short h=(unsigned short)t[i+j];
    while (j>0)
    {
        j--;
        h=(h*127)%101+(unsigned short)t[i+j];
    }
    return h%101;
}

void kr(string t, string p) ///dla pierwszysch 127 znaków z tablicy ASCII, wybrałem lp=101
{
    bool exist=false;
    unsigned tl=t.size(), pl=p.size(), i=0, j;
    if(tl<pl) cout << "Brak wzorca (wzorzec dluzszy od tekstu)" << endl;
    unsigned short ph=hasz(p, 0, pl), th;

    /*while (j>0)
    {
        j--;
        th=(th*127)%101+(unsigned short)t[j];
        ph=(ph*127)%101+(unsigned short)p[j];
    }
    ph%=101;
    th%=101;*/

    while (i<=tl-pl)
    {
        th=hasz(t, i, pl);
        if (ph==th)
        {
            j=0;
            while (j<pl && p[j]==t[i+j]) j++;
            if (j==pl)
            {
                cout << i << " ";
                exist=true;
            }
        }
        i++;
    }
    if(exist==false) cout << "Brak wzorca (nie znaleziono)" << endl;
}