パターン検索用の Rabin-Karp アルゴリズムの C プログラム

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

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

#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; }

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