C program of Rabin-Karp algorithm for pattern search-C++-php.cn

C program of Rabin-Karp algorithm for pattern search

Pattern Matching in C- We have to find if a string exists in another string, for example, the string "algorithm" exists in the string in "naive algorithm". If it is found, then its location (i.e. where it is located) is displayed. We tend to create a function that takes an array of 2 characters and returns the position if there is a match Otherwise, -1 is returned.

Input: txt = "HERE IS A NICE CAP" pattern = "NICE" Output: Pattern found at index 10 Input: txt = "XYZXACAADXYZXYZX" pattern = "XYZX" Output: Pattern found at index 0 Pattern found at index 9 Pattern found at index 12

Copy after login

Rabin-Karpis another pattern search algorithm. Just string matching Algorithm proposed by Rabin and Karp for finding patterns more efficiently Way. Like the naive algorithm, it also checks for patterns by moving the window It looks for hashes one by one, but doesn't need to check all characters in all cases. When the hashes match, each character is checked. This way, there is only one comparison per text subsequence, making it a more efficient pattern search algorithm.

Preprocessing time - O(m)

The time complexity of Rabin-Karp algorithm isO(m n), but for the worst Case, It isO(mn).

Algorithm

rabinkarp_algo(text,pattern,prime)

Input

rabinkarp_algo(text,pattern,prime)

Inputstrong>− Text and pattern. Find another prime number at the hash position

Output− Find the position of the pattern

Start pat_len := pattern Length str_len := string Length patHash := 0 and strHash := 0, h := 1 maxChar := total number of characters in character set for index i of all character in the pattern, do h := (h*maxChar) mod prime for all character index i of pattern, do patHash := (maxChar*patHash + pattern[i]) mod prime strHash := (maxChar*strHash + text[i]) mod prime for i := 0 to (str_len - pat_len), do if patHash = strHash, then for charIndex := 0 to pat_len -1, do if text[i+charIndex] ≠ pattern[charIndex], then break if charIndex = pat_len, then print the location i as pattern found at i position. if i < (str_len - pat_len), then strHash := (maxChar*(strHash – text[i]*h)+text[i+patLen]) mod prime, then if strHash < 0, then strHash := strHash + prime End

Copy after login

Example

Live demonstration

#include #include int main (){ char txt[80], pat[80]; int q; printf ("Enter the container string 
"); scanf ("%s", &txt); printf ("Enter the pattern to be searched 
"); scanf ("%s", &pat); int d = 256; printf ("Enter a prime number 
"); scanf ("%d", &q); int M = strlen (pat); int N = strlen (txt); int i, j; int p = 0; int t = 0; int h = 1; for (i = 0; i < M - 1; i++) h = (h * d) % q; for (i = 0; i < M; i++){ p = (d * p + pat[i]) % q; t = (d * t + txt[i]) % q; } for (i = 0; i <= N - M; i++){ if (p == t){ for (j = 0; j < M; j++){ if (txt[i + j] != pat[j]) break; } if (j == M) printf ("Pattern found at index %d ", i); } if (i < N - M){ t = (d * (t - txt[i] * h) + txt[i + M]) % q; if (t < 0) t = (t + q); } } return 0; }

Copy after login

Output

Enter the container string tutorialspointisthebestprogrammingwebsite Enter the pattern to be searched p Enter a prime number 3 Pattern found at index 8 Pattern found at index 21

Copy after login

The above is the detailed content of C program of Rabin-Karp algorithm for pattern search. For more information, please follow other related articles on the PHP Chinese website!