Question

Working modulo q = 11, how many spurious hits does the Rabin-Karp matcher encounter in the text T = 3141592653589793 when looking for the pattern P = 26? Select one: O a. 5 O b.4. O c. 6 6 O d. 7​

Answer 1

Answer:

buehenejdjdnejejendndjdjdnejsmsl

Answer 2

The number of times spurious hits the Rabin-Karp matcher encounter in the text T, when looking for the pattern P = 26 is 2 (None of the given options).

Given,

For string matching, working module q = 11.

Text T= 3141592653589793.

P=26.

To Find,

The number of times spurious hits does the Rabin-Karp matcher encounter in the text T.

Solution,

We can solve this numerical problem using the following definition and method.

The Rabin-Karp string matching algorithm creates a hash value for each M-character subsequence of text to be compared, as well as for the pattern itself.

The method will evaluate the pattern and the M-character sequence if the hash values are equal.

The algorithm will determine the hash value for the next M-character sequence if the hash values are uneven.

The algorithm or formula of Rabin-karp matcher is as follows,

RABIN-KARP-MATCHER (T, P, d, q)

• n is length [T]
• m is length [P]
• h is $d^{m-1}$ mod q
• p is  $\theta$
• $t_\theta$ is   $\theta$
• for i to 1 to m
• do p is (dp + P[i]) mod q
• $t_\theta$  is (d$t_\theta$ +T [i]) mod q
• for s is $\theta$ to n-m
• do if p = $t_s$
• then if P [1.....m] = T [s+1.....s + m]
• then "Pattern occurs with shift" s
• If s < n-m
• then ts+1 ←  (d ( $t_{s+1}$-T [s+1]h)+T [s+m+1])mod q.

Given, P=26.

The T  = 3141592653589793.

Here T.length = 16, hence, Q=16.

P mod Q = 26 mod 16=10.

Now find the exact match of P mod Q.

Now if S=0, 31 mod 16 = 15$\neq$ 10

If S=1, 14mod 11=3$\neq$ 10.

If S=2, 41mod11 $\neq$ 10.

S=3,15 mod 11 $\neq$ 10.

S=4,59mod 11 $\neq$ 10.

S=5, 92mod 11 $\neq$ 10.

S=6, 26mod 11 = 10.SPURIOUS HITS.

. . .65mod 11 $\neq$ 10.

. . .53mod 11 $\neq$ 10.

. . .35mod 11 $\neq$ 10.

. . .58mod 11 = 10.SPURIOUS HITS.

. . .89mod 11 $\neq$ 10.

. . .97mod 11 $\neq$ 10.

. . .79mod 11 $\neq$ 10.

. . .93mod 11 $\neq$ 10.

Therefore pattern P occurs only 2 shifts.

Hence, The number of times spurious hits the Rabin-Karp matcher encounter in the text T, when looking for the pattern P = 26 is 2 (None of the given options).

#SPJ3