Rabin karp algo

#1

wrong output

#2

you are just making rabin karp more complex. Use a simpler approach

See this code to get a better understanding over this algo.

#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
void search(char pat[],char text[],int q)
{
	int lenp=strlen(pat);// lenght of the pattern
	int lent=strlen(text);// lenght of text where pattern is to be checked
	int hashp=0; //hash value of the pattern
	int hasht=0; // hash value for checking the text hash value
	for(int i=0;i<lenp;i++)
	{
		hashp=hashp+int(pat[i])*pow(q,lenp-i-1);
	}
	for(int i=0;i<lent-lenp;i++)
	{
		for(int j=i;j<i+lenp;j++)
		{
			hasht=hasht+int(text[j])*pow(q,lenp-j-1+i);
		}
		if(hashp==hasht)
		{
			cout<<"string found at position "<<i<<endl;
		}
		hasht=0;
	}
}
int main()
{
	char text[20]="abcdabcabcdeac";
	char pat[10]="ab";
	int p=10;
	cout<<"text here is :"<<text<<endl;
	cout<<"pattern to be checked is :"<<pat<<endl;
	search(pat,text,p);
}

Output:

text here is :abcdabcabcdeac
pattern to be checked is :ab
string found at position 0
string found at position 4
string found at position 7

Thanks.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#4

There are 4 5 algorithms for string matching…which one should be preferred

1 Like
#5

KMP is most optimised as well as easy algorithm to match two strings. In my opinion you should always use kmp to match 2 strings.

#6

Don’t forget to give your feedback above. Thanks.

#7

Sir thn what is the need of doing 4 algorithms for same purpose cant i just ho through kmp algo?

#8

We included that in course so that you learn everything but you can leave other if you want.

#9

entire purpose of rolling hash was to do the search in linear time. You are doing it in polynomial time