## Lekcja – Wyszukiwanie wzorca w tekście – Rabin-Karp

```def generate_hash(text, pattern):

len_text = len(text)
len_pattern = len(pattern)
# lists with ordinals for charactes from the text and pattern
ascii_text = [ord(i) for i in text]
ascii_pattern = [ord(i) for i in pattern]

# calculate hash for pattern
hash_pattern = sum(ascii_pattern)

# calculate hash for text
len_hash_text = len_text - len_pattern + 1
hash_text = [0] * len_hash_text

for i in range(0, len_hash_text):
if i == 0:
hash_text[i] = sum(ascii_text[:len_pattern])
else:
hash_text[i] = (hash_text[i-1] - ascii_text[i-1] + ascii_text[i+len_pattern-1])

return [hash_text, hash_pattern]

def search_rabin_karp(text, pattern):

hash_text, hash_pattern = generate_hash(text, pattern) # hash_text has length of:   len_text - len_pattern + 1

len_text = len(text)
len_pattern = len(pattern)

result_list = []

for i in range(len(hash_text)):

if hash_text[i] == hash_pattern:               # it is possible that we have a match
matched_chars_count = 0
for j in range(len_pattern):
if pattern[j] == text[i+j]:
matched_chars_count += 1
else:
break                               # no - it is not a match, aborting!

if matched_chars_count == len_pattern:      # when matched_chars_count == len_pattern then the full pattern was in the text
result_list.append(i)
print(f"DEBUG: Found at index {i}")

return result_list

# source: http://www.jokes4us.com/peoplejokes/funnyrhymes.html'
text = "birdie, bidrie in the sky, dropped some white stuff in my eye, i'm a big girl i won't cry, i'm just glad that cows don't fly. - poem title: birdie"
pattern = 'birdie'
print(search_rabin_karp(text, pattern))

print([text[p:p+len(pattern)] for p in search_rabin_karp(text, pattern)])

```

## Rozwiązanie

```def generate_prefix(pattern):
pat_len = len(pattern)
pat_fun = [0] * pat_len
pref_len = 0    # length of the previous longest prefix suffix

if pat_len <= 1:   # eliminate trivial conditions
return pat_fun

pat_fun[0] = 0     # always 0
i = 1

while i < pat_len:
if pattern[i] == pattern[pref_len]:
pref_len += 1
pat_fun[i] = pref_len
i += 1
else:
# This is tricky. The pattern may contain multiple sub-prefixes. This allows to use them
if pref_len != 0:
pref_len = pat_fun[pref_len-1]
# we do not increment i here
# the loop will execute again for the same i and pref_len
# until a matching prefix would be found or we step down to pref_len == 0
else:
pat_fun[i] = 0
i += 1
return pat_fun

def search_kmp(pattern, text):
pat_len = len(pattern)
txt_len = len(text)
pat_fun = generate_prefix(pattern)

results_list = []

p = 0 # index pointing to pattern
t = 0 # index pointing to text

while t < txt_len:
if pattern[p] == text[t]:
# print('DEBUG: ', pattern[:p+1],'matches',text[:t+1])
t += 1
p += 1
if p == pat_len:
# print ('DEBUG: ', "Found pattern at index", t-p)
results_list.append(t-p)
p = pat_fun[p-1]
# print('DEBUG: ', 'p comes back to', p)
else:
if p != 0:
# print('DEBUG: ', 'Mismatch!', pattern[p], '<>', text[t], ' in ', pattern[:p+1], 'and', text[:t+1])
p = pat_fun[p-1]
# print('DEBUG: ', 't reamains', t, 'p comes back to', p, 'we will compare ', pattern[:p+1], 'with text', text[:t+1])
else:
# print('DEBUG: ', 'Mismatch! Return to start!', pattern[p], '<>', text[t])
t += 1
# print('DEBUG: ', 't increase to', t, 'p remains', p, 'we will compare', pattern[:p+1], 'with text', text[:t+1])

return results_list

def search_naive(pattern, text):

result_list = []

for text_start in range(len(text) - len(pattern) + 1):
found = True
for i in range(len(pattern)):
if pattern[i] != text[text_start+i]:
found = False
break
if found:
result_list.append(text_start)

return result_list

def generate_hash(text, pattern):

len_text = len(text)
len_pattern = len(pattern)
# lists with ordinals for charactes from the text and pattern
ascii_text = [ord(i) for i in text]
ascii_pattern = [ord(i) for i in pattern]

# calculate hash for pattern
hash_pattern = sum(ascii_pattern)

# calculate hash for text
len_hash_text = len_text - len_pattern + 1
hash_text = [0] * len_hash_text

for i in range(0, len_hash_text):
if i == 0:
hash_text[i] = sum(ascii_text[:len_pattern])
else:
hash_text[i] = (hash_text[i-1] - ascii_text[i-1] + ascii_text[i+len_pattern-1])

return [hash_text, hash_pattern]

def search_rabin_karp(pattern, text):

hash_text, hash_pattern = generate_hash(text, pattern) # hash_text has length of:   len_text - len_pattern + 1

len_text = len(text)
len_pattern = len(pattern)

result_list = []

for i in range(len(hash_text)):

if hash_text[i] == hash_pattern:               # it is possible that we have a match
matched_chars_count = 0
for j in range(len_pattern):
if pattern[j] == text[i+j]:
matched_chars_count += 1
else:
break                               # no - it is not a match, aborting!

if matched_chars_count == len_pattern:      # when matched_chars_count == len_pattern then the full pattern was in the text
result_list.append(i)
#                print(f"DEBUG: Found at index {i}")

return result_list

import random
import time

max_len = 1000000
allowed_chars = ['a', 'b']

print('Generating random text')
start = time.time()
text = ''.join(random.choice(allowed_chars) for i in range(max_len))
stop = time.time()
print(f'Text generation:    {stop - start}')

pattern = 'ababababababab'

print('Searching')
# checking time - naive search

start = time.time()
results_naive = search_naive(pattern, text)
stop = time.time()
print(f'Naive search:      found {len(results_naive)} matches in {stop - start} seconds')

# checking time - KMP search

start = time.time()
results_kmp = search_kmp(pattern, text)
stop = time.time()
print(f'KMP search:        found {len(results_kmp)} matches in {stop - start} seconds')

# checking time - Rabin-Karp search

start = time.time()
results_rk = search_rabin_karp(pattern, text)
stop = time.time()
print(f'Rabin-Karp search: found {len(results_rk)} matches in {stop - start} seconds')

```