First place a pattern appears in a text

Strings and tries Senior Python 3.13+ Kotlin 2.4+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
pat = "abab"
border = [0] * len(pat)
k = 0
for i in range(1, len(pat)):
    while k and pat[i] != pat[k]:
        k = border[k - 1]
    if pat[i] == pat[k]:
        k += 1
    border[i] = k
print(border)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A [0, 0, 1, 2]

Right: 'aba' ends with 'a' and 'abab' ends with 'ab'.

After a mismatch, the border says how much of the pattern is already matched, so the search never steps back in the text.

Why not the others?
  • B [0, 1, 2, 3]. A border must be shorter than the prefix itself.
  • C [0, 0, 1, 1]. 'abab' starts and ends with 'ab', a border of length 2.

30-second answer

Precompute, for each prefix of the pattern, the longest proper prefix that is also a suffix (its border). While scanning the text, on a mismatch fall back to the border instead of restarting, so text letters are never re-read. Both phases are linear: O(n + m) time, O(m) memory. This is the Knuth-Morris-Pratt algorithm.

Practise saying it · 60 s. No recording, just a timer

Explain linear-time pattern search.

Say your answer out loud, then check which of these points you covered:

  • Border table
  • Fall back, never re-read text
  • O(n + m)

Deep dive

The border table is the template; it also answers 'shortest repeating unit' questions.

A rolling hash (Rabin-Karp) is an alternative with a final character check.

The naive search is O(n × m) on inputs like 'aaaa…a' and 'aa…ab'.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def first_match(text: str, pat: str) -> int:
    if not pat:
        return 0
    # border[i]: length of the longest proper prefix of pat[:i + 1]
    # that is also a suffix of it
    border = [0] * len(pat)
    k = 0
    for i in range(1, len(pat)):
        while k and pat[i] != pat[k]:
            k = border[k - 1]  # fall back to a shorter border
        k += pat[i] == pat[k]
        border[i] = k
    k = 0  # letters of pat matched so far
    for i, ch in enumerate(text):
        while k and ch != pat[k]:
            k = border[k - 1]
        k += ch == pat[k]
        if k == len(pat):
            return i - k + 1
    return -1

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1
Kotlin 2.4
fun firstMatch(text: String, pat: String): Int {
    if (pat.isEmpty()) return 0
    // border[i]: longest proper prefix of pat[0..i] that ends it
    val border = IntArray(pat.length)
    var k = 0
    for (i in 1 until pat.length) {
        while (k > 0 && pat[i] != pat[k]) k = border[k - 1]
        if (pat[i] == pat[k]) k++
        border[i] = k
    }
    k = 0 // letters of pat matched so far
    for ((i, ch) in text.withIndex()) {
        while (k > 0 && ch != pat[k]) k = border[k - 1]
        if (ch == pat[k]) k++
        if (k == pat.length) return i - k + 1
    }
    return -1
}

Common mistakes

  • Restarting the pattern from 0 on every mismatch, which loses linear time.
  • Off-by-one in the border fall-back (use border[k - 1]).

Senior take & follow-ups

Explain the border table with one small example such as 'abab'.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do you find the shortest repeating unit of a string?

    Show hint

    len(s) - border[-1], if it divides len(s).

  2. When is a rolling hash nicer?

    Show hint

    When searching many patterns of the same length, or 2-D patterns.

What each operation costs: Trie · KMP Algorithm · Rabin Karp · String Matching

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.