• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

alg. Karpa-Rabina update hasha z modulo

Object Storage Arubacloud
0 głosów
254 wizyt
pytanie zadane 2 kwietnia 2022 w C i C++ przez Krzysztofs1234 Użytkownik (890 p.)

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;
}

 

Zaloguj lub zarejestruj się, aby odpowiedzieć na to pytanie.

Podobne pytania

0 głosów
2 odpowiedzi 382 wizyt
0 głosów
1 odpowiedź 700 wizyt
pytanie zadane 19 września 2017 w SPOJ przez Kamil Paradowski Użytkownik (620 p.)
0 głosów
1 odpowiedź 1,808 wizyt
pytanie zadane 20 maja 2017 w C i C++ przez Jakub 0 Pasjonat (23,120 p.)

92,680 zapytań

141,583 odpowiedzi

320,068 komentarzy

62,041 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...