The code shows an implementation of the Rabin-Karp algorithm in Python. Show step by step how the algorithm recognizes the given pattern. Use the given ascii table to analyze the algorithm.
The code shows an implementation of the Rabin-Karp algorithm in Python. Show step by step how the algorithm recognizes the given pattern. Use the given ascii table to analyze the algorithm.
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Related questions
Question
The code shows an implementation of the Rabin-Karp
![# Look for the occurrence of the pattern (leftmost) [0
# [0
# and thus quickly discard chains that do not correspond.
def rabin_karp(text, pattern):
... m -1] in the text
i +m -1]
n -1] using a hash function to test on each substring [i
...
...
Len(text)
Len(pattern)
n =
m =
P_hash =
t_hash
hashFunction (pattern, m)
hashFunction(text, m)
%3D
i = 0
while i <= n-m:
if p_hash ==t_hash:
found = True
# No matching no detected yet
# check individual characters
j = 0
while j < m and found:
if text[i+j] != pattern[j]: # # If no matching occurs, the inner loop ends
found = False
j += 1
if found:
# the loop ends with a no matching, so the substring starts at text[i]
return i
if i+m <= n-1:
# A matching is attempted with text[i+1 ... i+m]
t_hash = updateHashFunction (t_hash, text[i], text[i+m])
i += 1
return -1
# No matching found
# Returns the sum of the ASCII values of the characters in [0
def hashFunction(string, m):
i = 0
m-1]
...
sum = 0
while i < m:
sum += ord(string[i])
i += 1
return sum
# Update the hash function based on the previous
# value of the character that is no longer being taken into account
def updateHashFunction(previous_hash, old, new):
return previous_hash
ord(old) + ord(new)
('r',
's', 'i',
'c', 'o', 'n
pattern
text =
('a', 'm',"
index = rabin_karp(text, pattern)
print(index)](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F85a224de-fd77-41c6-b6c5-9a33b4be2ea2%2Fefce1bbd-32ed-4edb-b64b-73582112015e%2Fei3kobk_processed.jpeg&w=3840&q=75)
Transcribed Image Text:# Look for the occurrence of the pattern (leftmost) [0
# [0
# and thus quickly discard chains that do not correspond.
def rabin_karp(text, pattern):
... m -1] in the text
i +m -1]
n -1] using a hash function to test on each substring [i
...
...
Len(text)
Len(pattern)
n =
m =
P_hash =
t_hash
hashFunction (pattern, m)
hashFunction(text, m)
%3D
i = 0
while i <= n-m:
if p_hash ==t_hash:
found = True
# No matching no detected yet
# check individual characters
j = 0
while j < m and found:
if text[i+j] != pattern[j]: # # If no matching occurs, the inner loop ends
found = False
j += 1
if found:
# the loop ends with a no matching, so the substring starts at text[i]
return i
if i+m <= n-1:
# A matching is attempted with text[i+1 ... i+m]
t_hash = updateHashFunction (t_hash, text[i], text[i+m])
i += 1
return -1
# No matching found
# Returns the sum of the ASCII values of the characters in [0
def hashFunction(string, m):
i = 0
m-1]
...
sum = 0
while i < m:
sum += ord(string[i])
i += 1
return sum
# Update the hash function based on the previous
# value of the character that is no longer being taken into account
def updateHashFunction(previous_hash, old, new):
return previous_hash
ord(old) + ord(new)
('r',
's', 'i',
'c', 'o', 'n
pattern
text =
('a', 'm',"
index = rabin_karp(text, pattern)
print(index)
Transcribed Image Text:Caracteres de control ASCII
Caracteres ASCII imprimibles
DEC HEX
Simbolo ASCII
DEC HEX Simbolo DEC HEX Simbolo DEC HEX Simbolo
00h NULL
20h espacio
33
21h
00
(carácter nulo)
32
64
40h
96
60h
01
01h SOH (inicio encabezado)
65
41h
97
61h
a
02
02h
STX
(inicio texto)
34
22h
66
42h
98
62h
b
03
03h
ЕTX
35
23h
67
43h
99
63h
(fin de texto)
(fin transmisión)
(enquiry)
ACK (acknowledgement)
04
04h
EOT
36
24h
68
44h
100
64h
d
101 65h
102 66h
103 67h
05
05h
ENQ
37
25h
45h
69
70
e
06
06h
38
26h
46h
07
07h
BEL
(timbre)
39
27h
71
47h
08
08h
09h
BS
40
28h
72
48h
104
68h
105 69h
106 6Ah
107 6Bh
108 6Ch
109 6Dh
110 6Eh
111 6Fh
112 70h
113 71h
114 72h
115 73h
116 74h
(retroceso)
h
09
HT
41
29h
49h
(tab horizontal)
(salto de linea)
(tab vertical)
73
i
10
OAh
LF
42
2Ah
74
4Ah
J
K
11
VT
43
28h
75
4Bh
k
12
4Ch
OCh
ODh
FF
(form feed)
44
2Ch
76
13
CR
45
2Dh
77
4Dh
(retorno de carro)
(shift Out)
14
OEh
SO
46
2Eh
78
4Eh
n
SI
DLE
15
OFh
47
2Fh
79
4Fh
50h
51h
(shift In)
16
10h
(data link escape)
48
30h
80
(device control 1)
(device control 2)
(device control 3)
(device control 4)
NAK (negative acknowle.)
17
11h
DC1
49
31h
81
18
12h
50
DC2
DC3
32h
82
52h
R
19
13h
51
33h
83
53h
20
14h
DC4
52
34h
84
54h
21
15h
53
35h
85
55h
117
75h
u
22
16h
SYN
54
55
36h
86
56h
V
118
76h
(synchronous idle)
ETB (end of trans. block)
(cancel)
23
17h
37h
87
57h
58h
W
119
77h
w
24
18h
CAN
56
38h
120 78h
88
89
90
25
19h
EM
(end of medium)
57
39h
59h
Y
121
79h
y
122 7Ah
123 7Bh
26
1Ah
SUB
(substitute)
58
3Ah
:
SAh
1Bh
91
92
27
ESC
59
3Bh
5Bh
{
124 7Ch
125 7Dh
(escape)
28
1Ch
FS
60
3Ch
5Ch
(file separator)
(group separator)
(record separator)
29
1Dh
GS
61
3Dh
93
5Dh
}
126 7Eh
30
1Eh
RS
62
3Eh
>
94
SEh
31
1Fh
US
(unit separator)
63
3Fh
95
5Fh
127
20h
DEL
(delete)
©<BCDEFCHI
101 2345 6780 .. V | AC
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY