Project P090
Text search
Every place a pattern occurs in a text, found by the naive method, Knuth-Morris-Pratt and Boyer-Moore-Horspool, with the character comparisons each makes; KMP's failure table for a pattern; and the longest common prefix of a list of words.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-15
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
Every place a pattern occurs in a text, found three ways - the naive method, Knuth-Morris-Pratt and Boyer-Moore-Horspool - each counting the character comparisons it makes. Also KMP's table for a pattern, and the longest common start of a list of words. It starts with "she sells sea shells by the sea shore; ...".
main.eml- the menu, the text with its matches marked, and the reportsfinder.eml- the three searches, KMP's failure table, and the common prefix
How each part works:
- Naive, as in the corpus case
substring-search: try every starting place, comparing left to right until a character differs. - Knuth-Morris-Pratt: the table says, for each start of the pattern, how long its longest proper start is that is also its end - for abacabab, 0 0 1 0 1 2 3 2. On a mismatch the pattern slides on by that much instead of going back in the text. Each comparison either moves on in the text or slides the pattern on, and neither can happen more than n times, so it makes at most 2n comparisons for a text of n.
- Boyer-Moore-Horspool: compare from the pattern's last character backwards. After each try, slide by how far the text character under the pattern's end lies from the end of the pattern - or by the pattern's whole length if it does not occur in it. On ordinary text it skips most characters: 36 comparisons for "shells", against the naive 111.
- Matches may overlap; all three report every one.
- Longest common start, as in the corpus case
longest-common-prefix: go column by column until one word ends or two differ.
What is checked: menu choices 1 to 5; a pattern of 1 to 20 characters; 2 to 10 words; a text of 1 to 120 characters. An empty answer cancels.
Sessions: sessions/basic.in gives: - "she" (5 places), "shells" (3), "sea shore" (1) and "xyz" (none) in the starting text, with the comparisons of each method; - KMP's tables for abacabab and aaaa; - the common start of flower, flow and flight ("fl"), and of dog and cat (none); - a text of 29 a's and a b, searched for aaab: naive 108 comparisons, KMP 56, Horspool 30.
sessions/bad-input.in gives: - menu choices 0 and x; - a 21-character pattern, then empty patterns; - one word, and eleven; - a 121-character text, then a cancel.
Built on the verified corpus cases substring-search (trying every starting place) and longest-common-prefix (column by column).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== Text search ==
Every place a pattern occurs: naive, Knuth-Morris-Pratt and Boyer-Moore-Horspool, comparisons counted.
1) search 2) KMP table 3) common start of words 4) new text 5) quit
choice> 0
Pick a number from 1 to 5.
1) search 2) KMP table 3) common start of words 4) new text 5) quit
choice> x
Pick a number from 1 to 5.
1) search 2) KMP table 3) common start of words 4) new text 5) quit
choice> 1
pattern (1 to 20 characters)> xxxxxxxxxxxxxxxxxxxxx
A pattern is up to 20 characters.
1) search 2) KMP table 3) common start of words 4) new text 5) quit
choice> 1
pattern (1 to 20 characters)>
Cancelled.
1) search 2) KMP table 3) common start of words 4) new text 5) quit
choice> 2
pattern (1 to 20 characters)>
Cancelled.
1) search 2) KMP table 3) common start of words 4) new text 5) quit
choice> 3
words, separated by spaces (2 to 10)> one
Type 2 to 10 words.
1) search 2) KMP table 3) common start of words 4) new text 5) quit
choice> 3
words, separated by spaces (2 to 10)> w w w w w w w w w w w
Type 2 to 10 words.
1) search 2) KMP table 3) common start of words 4) new text 5) quit
choice> 4
text (1 to 120 characters)> yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
A text is up to 120 characters.
1) search 2) KMP table 3) common start of words 4) new text 5) quit
choice> 4
text (1 to 120 characters)>
Cancelled.
1) search 2) KMP table 3) common start of words 4) new text 5) quit
choice> 5
Bye.
What was typed (17 lines)
0
x
1
xxxxxxxxxxxxxxxxxxxxx
1
2
3
one
3
w w w w w w w w w w w
4
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
4
5
basic
interpreter: byte-equal== Text search ==
Every place a pattern occurs: naive, Knuth-Morris-Pratt and Boyer-Moore-Horspool, comparisons counted.
1) search 2) KMP table 3) common start of words 4) new text 5) quit
choice> 1
pattern (1 to 20 characters)> she
she sells sea shells by the sea shore; the shells she sells are sea shells for sure
^ ^ ^ ^ ^
'she' occurs 5 times, starting at character 0 14 43 50 68 (counting from 0).
All three methods find the same places.
Comparisons: naive 104, KMP 95 (never more than 2 x 83), Horspool 47.
1) search 2) KMP table 3) common start of words 4) new text 5) quit
choice> 1
pattern (1 to 20 characters)> shells
she sells sea shells by the sea shore; the shells she sells are sea shells for sure
^ ^ ^
'shells' occurs 3 times, starting at character 14 43 68 (counting from 0).
All three methods find the same places.
Comparisons: naive 111, KMP 97 (never more than 2 x 83), Horspool 36.
1) search 2) KMP table 3) common start of words 4) new text 5) quit
choice> 1
pattern (1 to 20 characters)> sea shore
she sells sea shells by the sea shore; the shells she sells are sea shells for sure
^
'sea shore' occurs 1 time, starting at character 28 (counting from 0).
All three methods find the same places.
Comparisons: naive 110, KMP 96 (never more than 2 x 83), Horspool 24.
1) search 2) KMP table 3) common start of words 4) new text 5) quit
choice> 1
pattern (1 to 20 characters)> xyz
she sells sea shells by the sea shore; the shells she sells are sea shells for sure
'xyz' does not occur.
All three methods find the same places.
Comparisons: naive 81, KMP 83 (never more than 2 x 83), Horspool 27.
1) search 2) KMP table 3) common start of words 4) new text 5) quit
choice> 2
pattern (1 to 20 characters)> abacabab
pattern a b a c a b a b
table 0 0 1 0 1 2 3 2
Each number is the longest proper start of the pattern so far that is also its end: after a mismatch there, the pattern can slide on and keep that many characters matched.
1) search 2) KMP table 3) common start of words 4) new text 5) quit
choice> 2
pattern (1 to 20 characters)> aaaa
pattern a a a a
table 0 1 2 3
Each number is the longest proper start of the pattern so far that is also its end: after a mismatch there, the pattern can slide on and keep that many characters matched.
1) search 2) KMP table 3) common start of words 4) new text 5) quit
choice> 3
words, separated by spaces (2 to 10)> flower flow flight
Longest common start: 'fl' (2 characters).
1) search 2) KMP table 3) common start of words 4) new text 5) quit
choice> 3
words, separated by spaces (2 to 10)> dog cat
They have no common start.
1) search 2) KMP table 3) common start of words 4) new text 5) quit
choice> 4
text (1 to 120 characters)> aaaaaaaaaaaaaaaaaaaaaaaaaaaaab
A text of 30 characters.
1) search 2) KMP table 3) common start of words 4) new text 5) quit
choice> 1
pattern (1 to 20 characters)> aaab
aaaaaaaaaaaaaaaaaaaaaaaaaaaaab
^
'aaab' occurs 1 time, starting at character 26 (counting from 0).
All three methods find the same places.
Comparisons: naive 108, KMP 56 (never more than 2 x 30), Horspool 30.
1) search 2) KMP table 3) common start of words 4) new text 5) quit
choice> 5
Bye.
What was typed (21 lines)
1
she
1
shells
1
sea shore
1
xyz
2
abacabab
2
aaaa
3
flower flow flight
3
dog cat
4
aaaaaaaaaaaaaaaaaaaaaaaaaaaaab
1
aaab
5
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
eml# P090 text search: every place a pattern occurs, found by the naive
# method, Knuth-Morris-Pratt and Boyer-Moore-Horspool, with the comparisons
# each makes; KMP's table for a pattern; and the longest common prefix.
import finder
def plain(s):
# Spaces at the ends removed (input keeps them otherwise).
0 => i
len(s) => j
while i < j and s[i] == " ":
i + 1 => i
while j > i and s[j - 1] == " ":
j - 1 => j
return s[i:j]
def joined(xs):
"" => s
for x in xs:
if s != "":
s + " " => s
s + str(x) => s
return s
def marks(n, places):
[" "] * n => row
for p in places:
"^" => row[p]
"" => s
for c in row:
s + c => s
len(s) => j
while j > 0 and s[j - 1] == " ":
j - 1 => j
return s[0:j]
def search(text):
plain(input("pattern (1 to 20 characters)> ")) => pat
if pat == "":
"Cancelled." ^0
return
if len(pat) > 20:
"A pattern is up to 20 characters." ^0
return
finder.naive(text, pat) => a
finder.kmp(text, pat) => b
finder.horspool(text, pat) => c
(" " + text) ^0
if len(a[0]) > 0:
(" " + marks(len(text), a[0])) ^0
if len(a[0]) == 0:
("'" + pat + "' does not occur.") ^0
else:
"times" => t
if len(a[0]) == 1:
"time" => t
("'" + pat + "' occurs " + str(len(a[0])) + " " + t + ", starting at character " + joined(a[0]) + " (counting from 0).") ^0
if a[0] == b[0] and b[0] == c[0]:
"All three methods find the same places." ^0
("Comparisons: naive " + str(a[1]) + ", KMP " + str(b[1]) + " (never more than 2 x " + str(len(text)) + "), Horspool " + str(c[1]) + ".") ^0
def table():
plain(input("pattern (1 to 20 characters)> ")) => pat
if pat == "" or len(pat) > 20:
"Cancelled." ^0
return
finder.failure(pat) => f
"" => top
"" => bot
for i in [0:len(pat) - 1]:
top + " " + pat[i] => top
bot + " " + str(f[i]) => bot
(" pattern" + top) ^0
(" table " + bot) ^0
"Each number is the longest proper start of the pattern so far that is also its end: after a mismatch there, the pattern can slide on and keep that many characters matched." ^0
def prefix():
plain(input("words, separated by spaces (2 to 10)> ")) => s
if s == "":
"Cancelled." ^0
return
[] => ws
"" => w
for c in s + " ":
if c == " ":
if w != "":
ws + [w] => ws
"" => w
else:
w + c => w
if len(ws) < 2 or len(ws) > 10:
"Type 2 to 10 words." ^0
return
finder.common_prefix(ws) => p
if p == "":
"They have no common start." ^0
else:
("Longest common start: '" + p + "' (" + str(len(p)) + " characters).") ^0
def new_text(text):
plain(input("text (1 to 120 characters)> ")) => s
if s == "":
"Cancelled." ^0
return text
if len(s) > 120:
"A text is up to 120 characters." ^0
return text
("A text of " + str(len(s)) + " characters.") ^0
return s
"she sells sea shells by the sea shore; the shells she sells are sea shells for sure" => text
"== Text search ==" ^0
"Every place a pattern occurs: naive, Knuth-Morris-Pratt and Boyer-Moore-Horspool, comparisons counted." ^0
True => running
while running:
"" ^0
"1) search 2) KMP table 3) common start of words 4) new text 5) quit" ^0
plain(input("choice> ")) => choice
if choice == "1":
search(text)
elif choice == "2":
table()
elif choice == "3":
prefix()
elif choice == "4":
new_text(text) => text
elif choice == "5":
False => running
else:
"Pick a number from 1 to 5." ^0
"Bye." ^0
Python projection (main.py)
import finder
def plain(s):
i = 0
j = len(s)
while i < j and s[i] == " ":
i = i + 1
while j > i and s[j - 1] == " ":
j = j - 1
return s[i:j]
def joined(xs):
s = ""
for x in xs:
if s != "":
s = s + " "
s = s + str(x)
return s
def marks(n, places):
row = [" "] * n
for p in places:
row[p] = "^"
s = ""
for c in row:
s = s + c
j = len(s)
while j > 0 and s[j - 1] == " ":
j = j - 1
return s[0:j]
def search(text):
pat = plain(input("pattern (1 to 20 characters)> "))
if pat == "":
print("Cancelled.")
return
if len(pat) > 20:
print("A pattern is up to 20 characters.")
return
a = finder.naive(text, pat)
b = finder.kmp(text, pat)
c = finder.horspool(text, pat)
print(" " + text)
if len(a[0]) > 0:
print(" " + marks(len(text), a[0]))
if len(a[0]) == 0:
print("'" + pat + "' does not occur.")
else:
t = "times"
if len(a[0]) == 1:
t = "time"
print("'" + pat + "' occurs " + str(len(a[0])) + " " + t + ", starting at character " + joined(a[0]) + " (counting from 0).")
if a[0] == b[0] and b[0] == c[0]:
print("All three methods find the same places.")
print("Comparisons: naive " + str(a[1]) + ", KMP " + str(b[1]) + " (never more than 2 x " + str(len(text)) + "), Horspool " + str(c[1]) + ".")
def table():
pat = plain(input("pattern (1 to 20 characters)> "))
if pat == "" or len(pat) > 20:
print("Cancelled.")
return
f = finder.failure(pat)
top = ""
bot = ""
for i in range(0, len(pat)):
top = top + " " + pat[i]
bot = bot + " " + str(f[i])
print(" pattern" + top)
print(" table " + bot)
print("Each number is the longest proper start of the pattern so far that is also its end: after a mismatch there, the pattern can slide on and keep that many characters matched.")
def prefix():
s = plain(input("words, separated by spaces (2 to 10)> "))
if s == "":
print("Cancelled.")
return
ws = []
w = ""
for c in s + " ":
if c == " ":
if w != "":
ws = ws + [w]
w = ""
else:
w = w + c
if len(ws) < 2 or len(ws) > 10:
print("Type 2 to 10 words.")
return
p = finder.common_prefix(ws)
if p == "":
print("They have no common start.")
else:
print("Longest common start: '" + p + "' (" + str(len(p)) + " characters).")
def new_text(text):
s = plain(input("text (1 to 120 characters)> "))
if s == "":
print("Cancelled.")
return text
if len(s) > 120:
print("A text is up to 120 characters.")
return text
print("A text of " + str(len(s)) + " characters.")
return s
text = "she sells sea shells by the sea shore; the shells she sells are sea shells for sure"
print("== Text search ==")
print("Every place a pattern occurs: naive, Knuth-Morris-Pratt and Boyer-Moore-Horspool, comparisons counted.")
running = True
while running:
print("")
print("1) search 2) KMP table 3) common start of words 4) new text 5) quit")
choice = plain(input("choice> "))
if choice == "1":
search(text)
elif choice == "2":
table()
elif choice == "3":
prefix()
elif choice == "4":
text = new_text(text)
elif choice == "5":
running = False
else:
print("Pick a number from 1 to 5.")
print("Bye.")
finder.eml
eml# P090 text search - every place a pattern occurs in a text, found three
# ways, each counting the character comparisons it makes, and the longest
# common prefix of a list of words.
def naive(text, pat):
# The corpus case substring-search: try every starting place, comparing
# left to right until a character differs. [places, comparisons].
len(text) => n
len(pat) => m
[] => found
0 => count
for i in [0:n - m]:
0 => j
True => going
while going and j < m:
count + 1 => count
if text[i + j] == pat[j]:
j + 1 => j
else:
False => going
if j == m:
found + [i] => found
return [found, count]
def failure(pat):
# Knuth-Morris-Pratt's table: for each prefix of the pattern, the length
# of the longest proper prefix that is also its suffix. A mismatch then
# says how far the pattern can slide without missing a match.
len(pat) => m
[0] * m => f
0 => k
for q in [1:m - 1]:
while k > 0 and pat[k] != pat[q]:
f[k - 1] => k
if pat[k] == pat[q]:
k + 1 => k
k => f[q]
return f
def kmp(text, pat):
# Never looks at a text character twice going forward: on a mismatch
# the pattern slides by the table instead. [places, comparisons]; the
# comparisons are at most 2n.
failure(pat) => f
len(pat) => m
[] => found
0 => count
0 => q
for i in [0:len(text) - 1]:
True => more
while more:
count + 1 => count
if text[i] == pat[q]:
False => more
q + 1 => q
elif q > 0:
f[q - 1] => q
else:
False => more
if q == m:
found + [i - m + 1] => found
f[q - 1] => q
return [found, count]
def horspool(text, pat):
# Boyer-Moore-Horspool: compare from the pattern's last character
# backwards, and after each try slide by how far the text character
# under the pattern's end is from the end of the pattern (or the whole
# length if it does not occur in the first m - 1). [places, comparisons].
len(text) => n
len(pat) => m
{} => shift
for j in [0:m - 2]:
m - 1 - j => shift[pat[j]]
[] => found
0 => count
0 => i
while i <= n - m:
m - 1 => j
True => going
while going and j >= 0:
count + 1 => count
if text[i + j] == pat[j]:
j - 1 => j
else:
False => going
if j < 0:
found + [i] => found
text[i + m - 1] => c
if c in shift:
i + shift[c] => i
else:
i + m => i
return [found, count]
def common_prefix(words):
# The corpus case longest-common-prefix: compare the words column by
# column until one ends or two differ.
if len(words) == 0:
return ""
words[0] => first
0 => k
while True:
if k >= len(first):
return first
for w in words:
if k >= len(w) or w[k] != first[k]:
return first[0:k]
k + 1 => k
Python projection (finder.py)
def naive(text, pat):
n = len(text)
m = len(pat)
found = []
count = 0
for i in range(0, n - m+1):
j = 0
going = True
while going and j < m:
count = count + 1
if text[i + j] == pat[j]:
j = j + 1
else:
going = False
if j == m:
found = found + [i]
return [found, count]
def failure(pat):
m = len(pat)
f = [0] * m
k = 0
for q in range(1, m):
while k > 0 and pat[k] != pat[q]:
k = f[k - 1]
if pat[k] == pat[q]:
k = k + 1
f[q] = k
return f
def kmp(text, pat):
f = failure(pat)
m = len(pat)
found = []
count = 0
q = 0
for i in range(0, len(text)):
more = True
while more:
count = count + 1
if text[i] == pat[q]:
more = False
q = q + 1
elif q > 0:
q = f[q - 1]
else:
more = False
if q == m:
found = found + [i - m + 1]
q = f[q - 1]
return [found, count]
def horspool(text, pat):
n = len(text)
m = len(pat)
shift = {}
for j in range(0, m - 2+1):
shift[pat[j]] = m - 1 - j
found = []
count = 0
i = 0
while i <= n - m:
j = m - 1
going = True
while going and j >= 0:
count = count + 1
if text[i + j] == pat[j]:
j = j - 1
else:
going = False
if j < 0:
found = found + [i]
c = text[i + m - 1]
if c in shift:
i = i + shift[c]
else:
i = i + m
return [found, count]
def common_prefix(words):
if len(words) == 0:
return ""
first = words[0]
k = 0
while True:
if k >= len(first):
return first
for w in words:
if k >= len(w) or w[k] != first[k]:
return first[0:k]
k = k + 1