KMP in Swift: How It Works and Why It Is Worth Learning

Introduction: Probably Not Your Next Interview Question

Let me be honest with you up front. You are probably never going to be asked to implement Knuth-Morris-Pratt in an interview. Most loops stop at two pointers, hash maps, DFS/BFS and the occasional graph/dp. KMP sits in that awkward middle ground where it is too specialised for a screening round and too well settled to come up in day-to-day work.

So why spend an afternoon on it?

Because IMHO, KMP has one genuinely beautiful idea, and that idea shows up everywhere once you learn to spot it. The idea is this, when something fails, you rarely have to throw away everything you learned before it failed. Most naive algorithms panic on failure and start over. KMP keeps its receipts.

That is a habit worth building, at least for me, and it generalises far past string matching. Caching, incremental parsing, resumable uploads, diffing algorithms, and stream processing all lean on the same instinct.

Here is the plan. We will understand the idea first with paper and pencil, then express it in Swift. If you only read one section, read the one about the LPS table. Everything else falls out of it.

What Is the KMP Algorithm?

KMP stands for Knuth-Morris-Pratt, named after Donald Knuth, James H. Morris, and Vaughan Pratt, who published it in 1977. It is an exact substring search algorithm. You will definitely find this one on LeetCode, as an easy level question, though the linear time complexity solution, and hence KMP, would be super hard level. You hand it a haystack and a needle, and it tells you where the needle appears in the haystack, character for character. No fuzzy matching, no wildcards, no regular expressions.

Let’s pin down the vocabulary, because the rest of the article depends on it:

• The text is the big string you are searching inside. We will call its length n.
• The pattern is the smaller string you are looking for. We will call its length m.
• The match index is the position in the text where the pattern starts.

The Whole Idea, in Four Letters

Before anything complicated, here is the entire trick in an example small enough to do in your head.

We are looking for the pattern AAB inside the text AAAB. Line them up and compare left to right:

text:     A A A B
pattern:  A A B
          ✓ ✓ ✗

The first A matches. The second A matches. Then the pattern wants a B but the text has an A, so we fail on the third comparison.

Now, what does the naive approach do? It gives up on this alignment completely, slides the pattern one step right, and starts comparing from the very beginning of the pattern again:

text:     A A A B
pattern:    A A B
            ^ start over from scratch

But look at what we just threw away. We already know the text has an A at that position, because we compared it a moment ago and it matched. Checking it again is wasted effort.

KMP notices something about the pattern itself. AAB starts with A, and the part we successfully matched (AA) ends with A. Those are the same letter. So the last A we matched can be reused as the first A of the next attempt. We keep it and pick up from the second letter:

text:     A A A B
pattern:    A A B
              ^ we already know the first A is fine, so resume here

From there, A matches A, then B matches B, and we have found the pattern at index 1.

That is KMP. Brute force discarded both matched letters. KMP kept one of them. The only reason it could keep one is that it looked at the pattern and noticed the pattern repeats its own beginning.

Everything else in this article is machinery for answering one question in advance: when a comparison fails, exactly how many letters do I get to keep? Answer that for every position in the pattern, store the answers in a small table, and you have the algorithm.

The Example We Will Use for Everything Else

Four letters is enough to see the idea, but too small to see it do anything impressive. For the detailed walkthrough we will use a longer pair and stay with it:

text:    A B A B D A B A C D A B A B C A B A B
index:   0 1 2 3 4 5 6 7 8 9 ...

pattern: A B A B C A B A B

The text is ABABDABACDABABCABAB and the pattern is ABABCABAB. Take a second to find the match by eye. It is there, and if it took you more than a moment, that is exactly the point. The text is full of near-misses that look like the pattern right up until they are not.

The answer, for the record, is index 10.

KMP vs. Naive String Search

How Brute Force Works

You already saw brute force with AAB. Line the pattern up, compare left to right, and on any mismatch slide forward exactly one position and restart from the beginning of the pattern. The only thing that changes on a longer pattern is how much you throw away each time:

text:    A B A B D A B A C D ...
pattern: A B A B C
                 ^ mismatch at text index 4

slide by one:
text:    A B A B D A B A C D ...
pattern:   A B A B C
           ^ mismatch immediately

Where the Repeated Work Comes From

Four comparisons bought us the knowledge that text positions 0 through 3 are exactly ABAB, and sliding by one throws all four away. The waste is not that brute force tries too many alignments, it is that it re-reads the same text characters over and over. In a bad case, like searching for AAAAB inside a long run of AAAAAAAA..., you match four characters, fail on the fifth, slide by one, and repeat. Every alignment does nearly m work, and there are nearly n alignments.

That gives brute force a worst-case time complexity of O(n * m).

In practice this often does not bite you, because on many real inputs the very first character rules out most alignments straight away. But “usually fine” is not the same as “fine”, and the failure mode is exactly the kind of repetitive, structured input you find in log files, DNA sequences, and binary protocols.

How the KMP Algorithm Works

Here is the same insight from the AAB example, stated generally this time.

When the pattern mismatches after a partial match, the characters that already matched came from the pattern itself, so we can consult the pattern to decide where to resume.

That turns the whole thing into a question about the pattern alone: given that we just matched the first 4 characters and then failed, what is the longest prefix of the pattern that is also a suffix of those 4 characters?

For ABAB, the answer is AB. So rather than restarting at pattern index 0, we resume at pattern index 2, because we already know the two characters sitting before our current text position are AB.

Notice what just changed. With AAB we salvaged a single letter, which you could fairly write off as a quirk of a pattern that happens to start with two As. Here we salvage two characters, and we do it because of a real two-character prefix that shows up again as a suffix. Once the amount you get to keep varies like that, a rule of thumb stops working and you want a lookup table.

The consequence is the part that makes KMP fast: the text index never moves backward. The pattern index slides around, and a single text character can be compared against several pattern positions while it does, but the text pointer itself only ever goes forward. We never rewind to re-examine text we have already passed.

Since we can answer that question purely from the pattern, we can answer it once, before the search even starts, and store the answers in a small table. That table is the LPS array.

Understanding the LPS Table

Proper Prefixes and Proper Suffixes

Two definitions, and they are simpler than they sound.

A prefix is any chunk taken from the start of a string. A suffix is any chunk taken from the end. The word proper just means “not the entire string”.

For the string ABAB:

Proper prefixes of ABAB	Proper suffixes of ABAB
A	B
AB	AB
ABA	BAB

Notice that ABAB itself appears in neither list. That is the “proper” restriction at work, and it is not just pedantry. If the whole string counted, then every string would trivially have itself as both a prefix and a suffix, the answer would always be “the whole thing”, and the table would tell us nothing. Excluding the full string is what forces the table to find real internal structure.

Comparing the two lists above, AB shows up in both. It is the longest string that is both a proper prefix and a proper suffix of ABAB, and its length is 2.

That number, 2, is exactly what the LPS table stores.

What LPS Actually Stores

LPS stands for Longest Proper Prefix which is also a Suffix. The table has one entry per character of the pattern, and the definition is:

lps[i] is the length of the longest proper prefix of pattern[0...i] that is also a suffix of pattern[0...i].

The important part is that each entry looks at a prefix of the pattern, not the whole pattern. lps[3] is about the first four characters only. This matters because when we mismatch at pattern index j, we have matched exactly j characters, and lps[j - 1] is the entry that describes them.

Operationally, here is how to read a value:

If you have matched j characters and then hit a mismatch, lps[j - 1] is the number of characters you can keep. Move the pattern index to lps[j - 1] and compare again, without touching the text index.

You will see this same idea called the prefix function or the failure function in other write-ups. “Prefix function” is normally this exact array. “Failure function” is the loosest of the three, since some presentations shift the values by one or use a -1 sentinel for “no fallback left”, so check the indexing convention before copying a table between sources. “Failure function” is arguably the most descriptive name though, since the whole point is telling you where to go when a comparison fails.

Warming Up on AAB

Start with the tiny pattern from earlier, because you can check it by eye.

i	pattern[0...i]	Longest prefix that is also a suffix	lps[i]
0	A	none, a single character has no proper prefix	0
1	AA	A	1
2	AAB	none, it starts with A and ends with B	0

So lps for AAB is [0, 1, 0].

Now read the middle entry back as an instruction. lps[1] = 1 says that if you have matched 2 characters and then fail, you get to keep 1 of them. That is exactly the single A we kept by hand a few sections ago, except now it is a number in a table instead of something you noticed.

Building the Table for ABABCABAB

Same procedure on the longer pattern. We go character by character, and at each step we ask: for the prefix ending here, what is the longest proper prefix that is also a suffix?

i	pattern[0...i]	Longest prefix that is also a suffix	lps[i]
0	A	none, a single character has no proper prefix	0
1	AB	none, A is not B	0
2	ABA	A	1
3	ABAB	AB	2
4	ABABC	none, nothing starts with C	0
5	ABABCA	A	1
6	ABABCAB	AB	2
7	ABABCABA	ABA	3
8	ABABCABAB	ABAB	4

So the complete table is:

pattern: A  B  A  B  C  A  B  A  B
index:   0  1  2  3  4  5  6  7  8
lps:     0  0  1  2  0  1  2  3  4

Two rows are worth pausing on.

Row 4 is the reset. We had built up to lps[3] = 2, meaning ABAB had a reusable prefix of length 2. Then C arrived. C does not extend AB into ABA, and it does not even match the first character A, so everything collapses to 0. A single unusual character can wipe out all accumulated structure, and that is correct behavior.

Row 8 is the payoff. lps[8] = 4 says that the last four characters of the full pattern (ABAB) are identical to the first four. That is what makes overlapping matches possible, and we will use it later when we search for every occurrence instead of just the first.

Now read the table back as instructions. If we mismatch at pattern index 4, we look at lps[3] = 2, so we resume at pattern index 2. If we mismatch at pattern index 8, we look at lps[7] = 3, so we resume at pattern index 3 and keep three characters of progress.

How to Build the LPS Array

Building the table by hand is fine for nine characters. Let’s turn it into an algorithm.

The Two Indices

We walk the pattern with two moving parts:

• i, the position we are currently computing an LPS value for. It starts at 1, because lps[0] is always 0 by definition.
• length, the length of the longest prefix-suffix we have successfully built so far. It starts at 0.

Here is the neat trick that makes this work. length does double duty. It is both a length (how many characters we have matched) and an index (the next character of the prefix we want to check). Because the prefix always starts at index 0, matching length characters means the next one to test is at index length.

When pattern[i] == pattern[length], the prefix-suffix grows by one. We increment length, record it in lps[i], and move i forward. Both pointers advance together.

Falling Back Without Starting Over

The interesting case is the mismatch, and it is the part most people find confusing on first read, so let’s go slowly.

Suppose pattern[i] != pattern[length] and length > 0. We have a prefix-suffix of some length that we cannot extend. The tempting move is to reset length to 0 and start over, but that would be the same mistake brute force makes.

Instead we set length = lps[length - 1].

Why does that work? Because the current prefix-suffix of length length is itself a string, and it has its own longest prefix-suffix, which we already computed. Dropping to lps[length - 1] gives us the next-longest candidate that is still guaranteed to be a valid suffix at our current position. The table falls back through itself.

Note that we do not advance i here. We retry the same character against a shorter candidate, and we may fall back several times in a row before either finding a match or hitting length == 0.

That is the special case: when length is already 0, there is no shorter prefix left to try. We write lps[i] = 0 and move on.

Two details that trip people up:

• Falling back does not move i. Only a match or a length == 0 mismatch moves i.
• We never re-examine already-written LPS values for correctness. Each is final once written.

The whole preprocessing pass costs O(m). It might look quadratic because of the inner fallback loop, but length only ever increases by 1 per outer step, so it can only decrease a total of m times across the entire run. That is a counting argument we will use again for the search phase.

Here it is in Swift:

private func buildLPS(_ pattern: [Character]) -> [Int] {
  var lps = [Int](repeating: 0, count: pattern.count)
  var length = 0
  var i = 1

  while i < pattern.count {
    if pattern[i] == pattern[length] {
      length += 1
      lps[i] = length
      i += 1
    } else if length > 0 {
      length = lps[length - 1]
    } else {
      lps[i] = 0
      i += 1
    }
  }

  return lps
}

Three branches, and each one maps directly to a paragraph above. The first extends a match. The second falls back through the table. The third gives up on this position.

How KMP Searches a String

With the table built, the search is almost anticlimactic.

Walking Through the Example

Let’s search for ABABCABAB inside ABABDABACDABABCABAB, using lps = [0, 0, 1, 2, 0, 1, 2, 3, 4]. Call the text index t and the pattern index p.

We start at t = 0, p = 0 and match four characters straight away:

text:    A B A B D A B A C D A B A B C A B A B
pattern: A B A B C
                 ^
t = 4, p = 4:  text 'D' vs pattern 'C'  →  mismatch

Here is the first interesting decision. We have matched 4 characters, so we consult lps[3] = 2. Set p = 2 and leave t at 4:

text:    A B A B D A B A C D A B A B C A B A B
pattern:     A B A B C
                 ^
t = 4, p = 2:  text 'D' vs pattern 'A'  →  mismatch again

Still no good. We have matched 2 characters, so consult lps[1] = 0. Set p = 0, t still at 4. Now p is 0 and D does not match A, so with no progress to preserve we advance the text index to t = 5.

From t = 5 we match ABA, then fail at t = 8 where the text has C but the pattern wants B at index 3. We consult lps[2] = 1, then lps[0] = 0, then advance. t = 9 is D, another immediate miss, so we advance to t = 10.

And from t = 10 everything lines up:

text:    A B A B D A B A C D A B A B C A B A B
pattern:                     A B A B C A B A B
                             ^^^^^^^^^^^^^^^^^
t reaches 19, p reaches 9 == pattern.count  →  match!

The match starts at t - p, which is 19 - 9 = 10. Exactly where we said it would be.

Now count the text characters we examined. Every index from 0 to 18, once each, plus a handful of extra comparisons at indices 4 and 8 where we fell back through the table. The text pointer never reversed. That is the whole win.

The Two Mismatch Cases

Every mismatch is one of two situations, and the distinction is the entire search loop:

Case 1: p > 0. Some of the pattern matched. We have real information to preserve, so we shrink the pattern index with p = lps[p - 1] and leave t alone. We are effectively sliding the pattern forward by more than one position, but we are doing it in a way that keeps the characters we already verified.

Case 2: p == 0. Nothing matched. There is nothing to preserve and no table entry to consult, so we advance t by one.

Neither case can skip a valid match. In case 2 the current text character does not match the pattern’s first character, so no match can start here. In case 1, lps[p - 1] is by definition the longest reusable prefix, so any alignment we skipped past would have required a longer prefix-suffix than the longest one, which cannot exist. The table’s maximality is what makes the jump safe.

Finding One Match or Every Match

For a single match, we return as soon as p reaches pattern.count. That gives us a familiar firstIndex-style API.

For every match, including overlapping ones, we do not return. We record the position and then set p = lps[p - 1], exactly the same fallback we use for a mismatch. This is why lps[8] = 4 mattered. After matching ABABCABAB, we keep the trailing ABAB as a head start on the next match.

Overlapping matches are easy to underestimate. Searching for AAA inside AAAAA has three answers, at indices 0, 1, and 2, not one. If you reset p = 0 after a match instead of falling back through the table, you will find only index 0 and silently miss the other two. Whether you want overlaps depends on the problem, but you should make that choice on purpose rather than by accident.

KMP Algorithm Implementation in Swift

Swift Strings Are Not Integer-Indexed

If you come from C or Java, the first thing you will notice is that text[5] does not compile in Swift.

The short version: a Swift Character is a grapheme cluster, which can be several Unicode scalars and many bytes. A family emoji like 👨‍👩‍👧‍👦 is one Character but 25 UTF-8 bytes. So you cannot jump to “character 5” without walking from the start and counting boundaries, which is why String.Index exists instead of integer subscripts.

KMP wants random access, and it jumps the pattern index around constantly. So we convert both inputs to [Character] once, up front:

let pattern = Array(pattern)
let text = Array(text)

That costs one O(n + m) pass and an allocation, which is a fair price for code that reads like the algorithm. A production API would work over String.UTF8View or [UInt8] instead.

There is a lot more to say about Swift’s string model, and it is genuinely a separate topic, so I plan to give it its own article on encoding, grapheme clusters, and the view types. For KMP, the two paragraphs above are all you need.

Building the LPS Array

We already wrote this one:

private func buildLPS(_ pattern: [Character]) -> [Int] {
  var lps = [Int](repeating: 0, count: pattern.count)
  var length = 0
  var i = 1

  while i < pattern.count {
    if pattern[i] == pattern[length] {
      length += 1
      lps[i] = length
      i += 1
    } else if length > 0 {
      length = lps[length - 1]
    } else {
      lps[i] = 0
      i += 1
    }
  }

  return lps
}

It is private because it is an implementation detail. Callers should not have to know the LPS table exists.

Writing the Search Function

Now the search. Note the name: kmpFirstIndex, not firstIndex. Swift’s standard library already gives every Collection a firstIndex(of:), and a free function with that name will shadow it inside a String extension, which produces a genuinely confusing compiler error. Pick a name that does not collide.

func kmpFirstIndex(of pattern: String, in text: String) -> Int? {
  let pattern = Array(pattern)
  let text = Array(text)

  guard !pattern.isEmpty else { return 0 }
  guard pattern.count <= text.count else { return nil }

  let lps = buildLPS(pattern)
  var t = 0
  var p = 0

  while t < text.count {
    if text[t] == pattern[p] {
      t += 1
      p += 1

      if p == pattern.count {
        return t - p
      }
    } else if p > 0 {
      p = lps[p - 1]
    } else {
      t += 1
    }
  }

  return nil
}

The behavior contract, stated plainly:

• Empty pattern returns 0. An empty string is found at the start of anything, which is what Swift’s own firstRange(of: "") does too.
• No match returns nil, matching the optional-returning convention you already expect from firstIndex(of:).
• A match returns the starting offset, computed as t - p at the moment p reaches the pattern length.

The pattern.count <= text.count guard is not strictly required for correctness, since the loop would exit on its own, but it saves us from building an LPS table we can never use.

One thing to watch: the returned Int is an offset into [Character], not a String.Index and not a byte offset. They coincide for ASCII and diverge the moment an emoji or combining accent shows up, so do not mix them.

If you want a real Range<String.Index> back, convert explicitly:

extension String {
  func firstRange(matchingKMP pattern: String) -> Range<String.Index>? {
    guard let offset = kmpFirstIndex(of: pattern, in: self) else { return nil }
    let start = index(startIndex, offsetBy: offset)
    let end = index(start, offsetBy: pattern.count)
    return start ..< end
  }
}

Note the cost, though. index(_:offsetBy:) walks from the start, so you just did an O(n + m) search and then paid another O(n) to describe the answer.

Supporting All and Overlapping Matches

Collecting every match is a two-line change to the loop. Instead of returning on a full match, append the position and fall back through the table:

func kmpAllIndices(of pattern: String, in text: String) -> [Int] {
  let pattern = Array(pattern)
  let text = Array(text)

  guard !pattern.isEmpty, pattern.count <= text.count else { return [] }

  let lps = buildLPS(pattern)
  var matches: [Int] = []
  var t = 0
  var p = 0

  while t < text.count {
    if text[t] == pattern[p] {
      t += 1
      p += 1

      if p == pattern.count {
        matches.append(t - p)
        p = lps[p - 1]
      }
    } else if p > 0 {
      p = lps[p - 1]
    } else {
      t += 1
    }
  }

  return matches
}

Note the empty-pattern behavior here differs from kmpFirstIndex, which returns 0. kmpAllIndices returns [] instead. That is a deliberate simplification rather than a principled choice, and it is worth knowing that Swift disagrees with both of us. "abc".ranges(of: "") yields four empty ranges, one at every boundary from 0 through 3. Matching that convention exactly means emitting n + 1 results for an empty pattern, which is rarely what a caller wants. Pick a behavior, write it in the doc comment, and be consistent across your own API.

The only new line that matters is p = lps[p - 1] after appending. Let’s see it earn its keep:

kmpAllIndices(of: "AAA", in: "AAAAA")    // [0, 1, 2]
kmpAllIndices(of: "ABAB", in: "ABABAB")  // [0, 2]

Both results include overlaps. For AAA, the LPS table is [0, 1, 2], so after a match at index 0 we keep two characters and immediately find index 1, then index 2. Reset to p = 0 instead and you get just [0], because the search resumes past the first match and never sees the other two.

The same thing happens with ABAB inside ABABAB. Falling back through lps[3] = 2 finds both index 0 and index 2. Resetting to p = 0 finds only index 0, since the occurrences overlap.

So if you specifically want non-overlapping matches, set p = 0 after appending. That is a deliberate, documented choice, not a bug, and it genuinely returns fewer results rather than the same ones by a slower route.

KMP Time and Space Complexity

KMP is O(n + m) time, and it is worth understanding why rather than memorizing it. There are two separate passes, and they add rather than multiply.

Preprocessing is O(m). We walk the pattern once to build the LPS table.

Searching is O(n). We walk the text once.

The part that deserves scrutiny is the fallback loop. In both phases there is an inner step that can run several times for a single outer character, which certainly looks quadratic. It is not, and the reason is a counting argument.

Focus on the search phase and watch the pattern index p. It increases by exactly 1 on each successful character match, and every successful match also advances the text index t. Since t only moves forward and stops at n, it advances at most n times, so p can increase at most n times in total. Every fallback strictly decreases p, and p never goes below 0. A value that goes up at most n times and never below zero cannot come down more than n times. So the total number of fallbacks across the entire search is bounded by n, not by n per character.

Amortized, the whole search is linear. The same argument applies to length during preprocessing.

Space is O(m) for the LPS table, which holds one integer per pattern character. That is genuinely small, and it depends only on the pattern, not on the text. A 20-character pattern needs a 20-element table whether you search a kilobyte or a gigabyte.

The [Character] conversion in our teaching implementation adds O(n + m) on top of that, which is worth calling out because it is an artifact of our convenience choice, not of KMP itself. An implementation that works directly over String.UTF8View or a byte buffer keeps the true O(m) space bound.

Closing Thoughts

If you want this to stick, trace ABABCABAB through ABABDABACDABABCABAB on paper. Build the LPS table by hand, then walk the search and write down t and p at every step. Ten minutes of that will teach you more than reading the code again.