Rabin-Karp string matching algorithm by rolling hash

Question

Here is an implementation of Rabin-Karp String matching algorithm in C#...

static void Main(string[] args)
{
  string A = "String that contains a pattern.";
  string B = "pattern";
  ulong siga = 0;
  ulong sigb = 0;
  ulong Q = 100007;
  ulong D = 256;
for (int i = 0; i < B.Length; i++)
{
    siga = (siga * D + (ulong)A[i]) % Q;
    sigb = (sigb * D + (ulong)B[i]) % Q;
}
if (siga == sigb)
{
    Console.WriteLine(string.Format(">>{0}<<{1}", A.Substring(0, B.Length), A.Substring(B.Length)));
    return;
}
ulong pow = 1;
for (int k = 1; k <= B.Length - 1; k++)
    pow = (pow * D) % Q;

for (int j = 1; j <= A.Length - B.Length; j++)
{
    siga = (siga + Q - pow * (ulong)A[j - 1] %Q) % Q;
    siga = (siga * D + (ulong)A[j + B.Length - 1]) % Q;
    if (siga == sigb)
    {
        if (A.Substring(j, B.Length) == B)
        {
            Console.WriteLine(string.Format("{0}>>{1}<<{2}", A.Substring(0, j), 
                                                             A.Substring(j, B.Length), 
                                                             A.Substring(j +B.Length)));
            return;
        }
    }
}
Console.WriteLine("Not copied!");

}

but it has one problem if i change the position of second string than it shows result not copied but

 string A = "String that contains a pattern.";
 string B = "pattern";

here it shows not copied

 string A = "String that contains a pattern.";
 string B = "Matches contains a pattern ";

i want to check whether it is copy from first string or not even i would add something in it it or change the position but it shouldn't make difference so how to change it that it would just compare the hashes of each word in string than implement it............

Related post - [Rabin Karp string matching algorithm](https://stackoverflow.com/q/10338379/465053) — RBT, May 14 '18 at 23:55

score 0 · Answer 1 · answered Dec 12 '11 at 16:44

0

Change

string B = "Matches contains a pattern ";

to

string B = "contains a pattern ";

and it will work

answered Dec 12 '11 at 16:44

but that is not a solution what if i use two input file and want check them and second file is being edited by changing its position each and everything is there but it is copied so how would we check this????????????? – Rdx Dec 12 '11 at 16:55
in this case what you have is not enough. check the http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm#Rabin.E2.80.93Karp_and_multiple_pattern_search – Dec 12 '11 at 17:10

Rabin-Karp string matching algorithm by rolling hash

1 Answers1