Question

Napisać program, który dla podanego przez użytkownika tekstu i wzorca wyszuka wszystkie wystąpienia wzorca z tekście przy użyciu algorytmu Karpa-Rabina. C++

Answer 1

Starałem się możliwie prostą implementację, proszę o naj.

 

#include <iostream>
#include <cstdio>
using namespace std;
unsigned long long haszt,haszw,pot=2,pot2;
int n,m;
string wzorzec,tekst;
int main()
{

     cout<<"Podaj wzorzec: \n";
     cin>>wzorzec;

     cout<<"Podaj tekst: \n";
     cin>>tekst;  
     m=wzorzec.size();
     n=tekst.size();     
     for(int i=0;i<m;i++)
     {
      haszw=haszw*pot+wzorzec[i];
      haszt=haszt*pot+tekst[i];
     }
     pot2=1;
     for(int i=0;i<m;i++)
     {
      pot2*=pot;
     }     
     for(int i=0;i<n-m+1;i++)
     {    
      if(haszt==haszw)
      {
          cout<<i+1<<" ";
      }
      haszt=haszt*pot+tekst[i+m];
      haszt-=tekst[i]*pot2;
     }
}