Rabin Karp Algorithm

A military group is monitoring messages from terrorists which are transmitted as binary coded data streams.

(a) The military is looking for an efficient way to search an identified pattern in the serial stream, in the data so far monitored, at a given time. In this setting, suppose the message T[1 ...n] is being transferred serially, in the order T[1],T[2],.... the military is interested in checking if the text seen so far contains a pattern P, where P has length m. Every time when the next letter of the text T is transmitted, it is necessary to check if the text seen so far contains P.

(b) Now the terrorists are broadcasting reversed messages of the original message. So that although the same pattern P is used, the text T[1 ...n] is being transferred in reverse. That is, in the order T[n],T[n−1],... .Modify your algorithm so that it still detects the occurrence of P in the text T[i...n] immediately (i.e., in constant time) after the letter T[i] is seen.

Implementation in C#

Military.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace StringMatching
{
    class Military
    {
        public static void Main(string[] args)
        {

            string text = "dabrabracabaracadabrabrabacarbracad";
            string pattern = "bracaba";
            string reverse = "";
            //Reverse the text string
            for (int i = (text.Length - 1); i >= 0; i--)
                reverse += text[i];

            Military m = new Military();
            m.showText(text, pattern);
            m.showReverse(reverse, pattern);
            Console.ReadKey();

        }
        //Show the matching of text and pattern
        private void showText(string text, string pattern) {

            RabinCarp rc = new RabinCarp(pattern);
            int offset = rc.Match(text);

            if (offset != text.Length)
                Console.WriteLine("\nText is matching Success.........................");
            else
                Console.WriteLine("\nText is not matching.............................");

            Console.WriteLine("text :    " + text);//Print the text

            Console.Write("Pattern : ");//Print the pattern along the text
            for (int i = 0; i < offset; i++)
            {
                Console.Write(" ");
            }
            Console.WriteLine(pattern);

        }
        //Show the matching of reverse text and pattern
        private void showReverse(string reverse, string pattern) {

            RabinCarp rc = new RabinCarp(pattern);
            int offset = rc.Match(reverse);

            if (offset != reverse.Length)
                Console.WriteLine("\nReverse text is matching Success.................");
            else
                Console.WriteLine("\nReverse text is not matching.....................");

            Console.WriteLine("text :    " + reverse);//Print the reverse text

            Console.Write("Pattern : ");//Print the pattern along the reverse text
            for (int i = 0; i < offset; i++)
            {
                Console.Write(" ");
            }
            Console.WriteLine(pattern);

        }
    }
}

RabinCarp.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace StringMatching
{
    class RabinCarp
    {
        private string pattern;
        private int m, h, patternHash, q;

        public RabinCarp(string pattern)
        {
            this.pattern = pattern;//Set the pattern
            this.m = pattern.Length;//Set the pattern length
            this.q = 13;//Modulus prime number
            this.h = ((int)Math.Pow(10, m - 1)) % q;
            this.patternHash = Hash(pattern);//Generate the pattern hash value
        }
        //Hash value Generating function
        private int Hash(string text)
        {
            int hashVal = 0;
            for (int i = 0; i < m; i++)
                hashVal = (10 * hashVal + text[i]) % q;
            return hashVal;
        }
        //Check whether the pattern and text are match
        private bool Check(string text, int offset)
        {
            for (int i = 0; i < m; i++)
            {
                if (pattern[i] != text[offset + i])
                    return false;
            }
            return true;
        }
        //Check for exactly matching
        public int Match(string text)
        {
            int n = text.Length;
            if (n < m)
                return n;//Return the text length
            int textHash = Hash(text);//Generate the text hash value

            //Checking whether offset is 0
            if (patternHash == textHash && Check(text, 0))
                return 0;

            //Check for the hash match and exact match
            for (int i = m; i < n; i++)
            {
                //Remove the high order digit and add the new low order digit
                textHash = (textHash + q - h * text[i - m] % q) % q;
                textHash = (textHash * 10 + text[i]) % q;

                //Check whether the exact matching pattern and text
                int offset = i - m + 1;
                if (patternHash == textHash && Check(text, offset))
                    return offset;
            }
            //Matching is unsuccess
            return n;
        }
   
    }
}