• 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

Aruba Cloud PRO i VPS, Openstack, VMWare, MS Hyper-V
0 głosów
70 wizyt
pytanie zadane 2 kwietnia w C i C++ przez Krzysztofs1234 Użytkownik (780 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 244 wizyt
0 głosów
1 odpowiedź 561 wizyt
pytanie zadane 19 września 2017 w SPOJ przez Kamil Paradowski Użytkownik (620 p.)
0 głosów
1 odpowiedź 1,097 wizyt
pytanie zadane 20 maja 2017 w C i C++ przez Jakub 0 Pasjonat (23,100 p.)

89,727 zapytań

138,332 odpowiedzi

309,340 komentarzy

59,649 pasjonatów

Advent of Code 2022

Top 15 użytkowników

  1. 429p. - Argeento
  2. 427p. - nidomika
  3. 396p. - Mikbac
  4. 392p. - ssynowiec
  5. 390p. - Łukasz Eckert
  6. 387p. - TheLukaszNs
  7. 386p. - rucin93
  8. 382p. - Michal Drewniak
  9. 382p. - Marcin Harasimowicz
  10. 378p. - JMazurkiewicz
  11. 373p. - tokox
  12. 367p. - Jarosław Roszyk
  13. 362p. - adrian17
  14. 359p. - overcq
  15. 350p. - Mawrok
Szczegóły i pełne wyniki

Motyw:

Akcja Pajacyk

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

Sklep oferujący ćwiczenia JavaScript, PHP, rozmowy rekrutacyjne dla programistów i inne materiały

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...