Using the Rabin Karp algorithm, find the pattern string in the given text. Pattern: “fed”, Text: “acfeddadfdec”. Write all the steps involved.
Choose the hash function:q=101x=10hash[fed]=(102⋅102+101⋅10+100)mod101=99i=1:hash[acf]=(97⋅102+99⋅10+102=10792)mod101=86≠99i=2:hash[cfe]=(99⋅102+102⋅10+101)mod101=12≠99i=3:hash[fed]=(102⋅102+101⋅10+100)mod101=99End of procedure.Position 3.Choose\,\,the\,\,hash\,\,function:\\q=101\\x=10\\hash\left[ fed \right] =\left( 102\cdot 10^2+101\cdot 10+100 \right) mod101=99\\i=1: hash\left[ acf \right] =\left( 97\cdot 10^2+99\cdot 10+102=10792 \right) mod101=86\ne 99\\i=2: hash\left[ cfe \right] =\left( 99\cdot 10^2+102\cdot 10+101 \right) mod101=12\ne 99\\i=3: hash\left[ fed \right] =\left( 102\cdot 10^2+101\cdot 10+100 \right) mod101=99\\End\,\,of\,\,procedure. Position\,\,3.\\Choosethehashfunction:q=101x=10hash[fed]=(102⋅102+101⋅10+100)mod101=99i=1:hash[acf]=(97⋅102+99⋅10+102=10792)mod101=86=99i=2:hash[cfe]=(99⋅102+102⋅10+101)mod101=12=99i=3:hash[fed]=(102⋅102+101⋅10+100)mod101=99Endofprocedure.Position3.
Need a fast expert's response?
and get a quick answer at the best price
for any assignment or question with DETAILED EXPLANATIONS!
Comments
Leave a comment