C++ Rabin-Karp Algorithm

Açıklama

• Rabin Karp Algoritması aranacak kelimeyi hashcode çevirerek metin içersinde arama işlemidir.
• Hashcode çevirme işlemi sonucu çıkan şey sayı olacağı için kelimeyi metin ile karşılaştırmadan önce metinide aynı şekilde hashcode çevirerek karşılaştırma yapmaktadır.

Kod

#include <stdio.h> 
#include <string.h> 
#include <iostream>
#include <string>
#include <sys/time.h>
#include <cmath>


// MEHMET ERIM RABIN-KARP

using namespace std;


int W = 997;
int S = 256;


unsigned int hash(string s,int len){
	
	unsigned int h = 0;
	for(int k=0;k<len;k++){
		h=(h*S+s[k])%W;
	}

	return h;
}


void search(string pattern, string text) 
{ 

 	int m = pattern.size();
    int n = text.size();
    
    cout <<	"Size of text = "<< n << endl ;
    cout <<	"Size of pattern = "<< m << endl ;
	
    int patternHash = 0; // pattern hashcode
    int textHash = 0; // text hashcode
    int SPower = 1;
        
        
    //to Canculate SPOWER 
  	  for (int i = 0; i < m - 1; i++)  
        SPower = (SPower * S) % W;  
  
        
 //   cout << "SPower = "<< SPower << endl;

	// hashing
    for (int i = 0; i < m; i++)
    {
        patternHash = (S*patternHash + pattern[i])%W;
        textHash = (S*textHash + text[i])%W;
    }
 

    for (int i = 0; i <=(n-m); i++)
    {

        if (patternHash == textHash)
        {
			printf("Pattern found at index %d \n", i);
        }
 
 
     	// rehashing
        textHash = ((S*(textHash - text[i]*SPower) + text[i+m])%W+W)%W;
        
      //  cout << patternHash << " " << textHash << endl;
    
    }

}

int main() 
{ 	

	string pattern = "AA";
	string text = "AA";

	search(pattern,text);
    
    return 0; 
}