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)])
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')