<!-- canonical: https://efficientnewlanguage.org/eml-p/projects/P090-text-search/ | updated: 2026-10-15 -->

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

EML-P project `projects/text-search` in the EML language repo: 2 module(s), entry `main.eml`, terminal UI. There, `eml project run projects/text-search` runs it and `eml project verify projects/text-search` replays every session under CPython (two hash seeds) and in the interpreter; the site build replays every session in the interpreter again and publishes a session only if its screen matches.

Built on verified corpus cases: substring-search (https://efficientnewlanguage.org/cases/106-substring-search/), longest-common-prefix (https://efficientnewlanguage.org/cases/102-longest-common-prefix/).

## Sessions

### bad-input - interpreter: byte-equal to the golden

Input:

```text
0
x
1
xxxxxxxxxxxxxxxxxxxxx
1

2

3
one
3
w w w w w w w w w w w
4
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
4

5
```

Screen:

```text
== 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.
```

### basic - interpreter: byte-equal to the golden

Input:

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

Screen:

```text
== 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.
```

## Modules

### main.eml

```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 of main.eml:

```python
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 of finder.eml:

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

## README

# P090 - Text search

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 reports
- `finder.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).