### Robin-Karp String Searching Algorithm

**Problem Statement:** Write an efficient algorithm for matching the pattern given by the user in a string. If the pattern exists print the starting indexes in the string else return 1.

**Method 1- Brute Force Approach**

Lets us look what is problem with the Brute-Force Approach for the string matching

Let the length of String T will be n.

And length of Pattern P will be m.

Since the length of T is n , we have n-m+1 possible choices for comparisons.

The following Algorithms check for the first occurrence of the pattern P in the string T.

Code:-

#include<iostream.h> #include<string.h> using namespace std; int search(int T[], int P[] ) { int n=strlen(T); int m=strlen(P); for(int i=0;i<=n;i++) // This loop can also be used to run till n-m //, but if we have element matching after n-m location , then the loop should run upto n. { int j=0; while(j<m && P[j]==T[i+j]) //character matching of pattern ans string j=j+1; if(j==m) return i; } } int main() { char T[] = "AABAACAADAABA"; char P[] = "AABA"; search(T,P); return 0; }

The time complexity of the Brute Force approach is O(n*m).

**Method 2:- Robin- Karp String Matching Algorithm**

Robin karp Algorithm is a string searching algorithm that uses hashing technique and instead of checking for each possible position in T (i.e String T ), we only check that the hashing of P (i.e pattern P ) and hashing of T gives the same result

Using , this approach the time complexity can be reduced to O(n+m) for the best and average cases.

But for the worst case , the complexity is increased to O(m*n).

m=strlen(T)

n=strlen(P)

Steps:- 1: Initailly , we have to find the hash value of Patter T and first text of String T P_hash=0 , T_hash=0 For finding the hash value , we have 256 characters in ASCII . Formula for finding hash functionP_hash:= (maxchar*P_hash + P[i])% primeT_hash:= (maxchar*T_hash + T[i])% prime2:- After finding the hash function of first text window , we will slide over the String T one by one. 3:- Now in the loop , we will check if the hash function of String T and Pattern T matches or not . If it maches, we will check the elements of the Pattern P with string T , and we return the indexes. 4:- Now, we calcuate the hash function after sliding the window by one , by removing the leading character and adding the trailing character. For this calculation of hash function is done by the formula:- T_hash=(maxchar*(T_hash-T[i]*h +T[i+m])%prime If hash function comes out to be negative , make it positive by adding the prime number.

Code:–

#include<iostream> #include<string.h> #define max_char 256 using namespace std; void robin_karp(char P[], char T[], int prime) { int m = strlen(P); int n = strlen(T); int i, j; int p_hash = 0; // hash value for pattern int t_hash= 0; // hash value for string int h = 1; for (i = 0; i < m-1; i++) h = (h*max_char)%prime; for (i = 0; i < m; i++) { p_hash = (max_char*p_hash + P[i])%prime; //hash value of pattern t_hash = (max_char*t_hash + T[i])%prime; //hash value of string } for (i = 0; i < n ;i++) // Slide the pattern over text one by one { if ( p_hash == t_hash ) //check if two hash value is equal or not. { /* Check for characters one by one */ for (j = 0; j < m; j++) { if(T[i+j] != P[j]) break; } // if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1] if(j == m) cout<<"Pattern matched at index "<<i<<endl; } if ( i < n-m ) { t_hash = (max_char*(t_hash - T[i]*h) + T[i+m])%prime; // Calculate hash value for next window of text: Remove // leading digit, add trailing digit if (t_hash < 0) //for negative value of t_hash , make it positive by adding prime. t_hash = (t_hash + prime); } } } int main() { char T[] = "AABAACAADAABAABA"; char P[] = "AABA"; int prime = 101; // A prime number robin_karp(P, T, prime); return 0; }

output:- Pattern matched at index 0 Pattern matched at index 9 Pattern matched at index 12

CommentsNo comment yet.