Add Rabin-Karp search algorithm

danghai · danghai · commit bb7199d70649 · 2019-05-10T17:42:24.000-07:00
diff --git a/searching/pattern_search/rabin_karp_search.c b/searching/pattern_search/rabin_karp_search.c
@@ -0,0 +1,65 @@
+#include <stdio.h>
+#include <string.h>
+
+/* Kabin-Karp algorithm for pattern searching
+   d: radix-d notation. Ex. number from 0->9, d = 10
+   q: prime number for hashing */
+void rabin_karp_search(char *str, char *pattern, int d, int q)
+{
+    int len_str = strlen(str);
+    int len_pat = strlen(pattern);
+    int i, h = 1;
+    int hash_s = 0; /* hash value for string text */
+    int hash_p = 0; /* hash value for pattern */
+
+    /* h = pow(d, len_pat - 1) % q */
+    for(i = 0; i < len_pat - 1; i++)
+        h = d * h % q;
+    /* Calculating hashing of pattern and the 1st window of text */
+    for(i = 0; i < len_pat; i++)
+    {
+        hash_p = (d*hash_p + pattern[i]) % q;
+        hash_s = (d*hash_s + str[i]) % q;
+    }
+
+    for(i = 0; i <= len_str - len_pat; i++)
+    {
+        /* Check hash value of current window of text, and pattern
+           If it is match, check each character to make sure pattern
+           is match with current window of text */
+        if (hash_p == hash_s)
+        {
+            int j;
+            for(j = 0; j < len_pat; j++)
+            {
+                if(pattern[j] != str[i + j])
+                    break;
+            }
+            if(len_pat == j)
+                printf("--Pattern is found at: %d\n", i);
+        }
+        /* Calculate hash value for next window by removing the leading
+           element of current window text, and adding its trailing */
+        hash_s = (d*(hash_s -str[i]*h) + str[i + len_pat]) % q;
+        /* Converting hash value to positive when it is negative */
+        if (hash_s < 0)
+            hash_s = hash_s + q;
+    }
+}
+
+int main()
+{
+    char str[] = "AABCAB12AFAABCABFFEGABCAB";
+    char pat1[] = "ABCAB";
+    char pat2[] = "FFF";    /* not found */
+    char pat3[] = "CAB";
+
+    printf("String test: %s\n", str);
+    printf("Test1: search pattern %s\n", pat1);
+    rabin_karp_search(str, pat1, 256, 29);
+    printf("Test2: search pattern %s\n", pat2);
+    rabin_karp_search(str, pat2, 256, 29);
+    printf("Test3: search pattern %s\n", pat3);
+    rabin_karp_search(str, pat3, 256, 29);
+    return 0;
+}
