## Lekcja – Wyszukiwanie wzorca w tekście – Knuth-Morris-Pratt

```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

pattern = 'SQSQR'
generate_prefix(pattern)

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

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)
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:
t += 1
print('DEBUG: ', 't increase to', t, 'p remains', p, 'we will compare', pattern[:p+1], 'with text', text[:t+1])

pattern = 'SQSQR'
text = 'SQSQXSQXSQSQSQR'
search_pattern(pattern, text)

pattern = 'ACxACAC'
print(f"{pattern} - {generate_prefix(pattern)}")
search_pattern(pattern, 'AC--ACxA-A--ACxACACxACAC-')

```

## 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:
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

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

```