Question

Complete the following questions:

1. Apply the Horspool algorithm to determine the location of the pattern “BABOON” within the text: “KARL_SAW_THE_BABOON”.

2. Given the following input data: 50, 18, 62 55, 81, 77, 54, construct both the “open” and “closed” hash tables.

Answer 1

1. To implement the Horspool algorithm first a shift table need to be prepared. The shift table will define the number of shift need to be taken for each character of the string.

Here the pattern is, "BABOON"

No. of Character: 6

So the number of shift for the character of the pattern will be B = 5, A = 4, B = 3 (Overwrite the value 5), O = 2, O = 1 (Overwrite the value 2) and N will not be considered here.

The number of shift for the character of the string will be 6.

The final shift table is given below:

character c	A	B	E	H	K	L	N	O	R	S	T	W	_
shift t (c)	4	3	6	6	6	6	6	1	6	6	6	6	6

Now the algorithm will start:

K

A

R

L

_

S

A

W

_

T

H

E

_

B

A

B

O

O

N

B

A

B

O

O

N

N is not equal to S. So the pattern will be shifted by 6 characters (From the shift table for character S).

K

A

R

L

_

S

A

W

_

T

H

E

_

B

A

B

O

O

N

B

A

B

O

O

N

N is not equal to E. So the pattern will be shifted by 6 characters (From the shift table for character E).

K

A

R

L

_

S

A

W

_

T

H

E

_

B

A

B

O

O

N

B

A

B

O

O

N

  N is not equal to O. So the pattern will be shifted by 1 character (From the shift table for character O).

K

A

R

L

_

S

A

W

_

T

H

E

_

B

A

B

O

O

N

B

A

B

O

O

N

And the pattern finally matched. So the algorithm end.

2. To construct the open and close hash table a hash function H(K) = K mod n is needed. As the number of input is 7, let the hash function is H(K) = K mod 7.

Open Hash Table:

50 % 7 = 1

18 % 7 = 4

62 % 7 = 6

55 % 7 = 6

81 % 7 = 4

77 % 7 = 0

54 % 7 = 5

0	1	2	3	4	5	6
77	50			18	54	62
				81		55

Closed Hash Table:

In a closed hash table if a collision (two data on the same position) occurs then the data will be shifted to the next empty cell.

As 55 should be in 6th cell, but there would be a collision so it would be shifted to 7th cell.

As 55 should be in 4th cell, but there would be a collision so it would be shifted to 5th cell.

As 54 should be in 45h cell, but there would be a collision so it would be shifted to 8th cell.

0	1	2	3	4	5	6	7	8
77	50			18	81	62	55	54