Introduction

This article was started by LeoRiether and concluded by me. I found his idea incredible and offered to help him finishing the text he started to write here some years ago. I hope everyone finds it interesting! I think it's the most natural way to understand the KMP algorithm.

When following the examples, you should use LeoRiether's KMP simulator to see for you yourself what is happening.

The definitions presented here will not be so rigorous, but will instead follow a more intuitive approach. We will use examples with strings composed of characters from $$$a$$$ to $$$z$$$, but you could do the exact same with any other alphabet (like the natural numbers or whatever you want).

Automaton?

The text will assume you know what is a nondeterministic finite automaton (NFA) and a deterministic finite automaton (DFA), but I believe that an intuitive comprehension of them is enough to understand the ideas presented. You can think of an automaton as a graph with letters in the edges, where we will call vertices states. There is a starting state and some accepting states. To use an automaton, you maintain "pointers" to it's states/vertices, which will be called "threads".

Feeding a string $$$S$$$ to an nondeterministic finite automaton as input is to feed all of it's characters $$$S_i$$$ sequentially, considering that at the start there is a thread at the starting state. To feed a character to an automaton is basically to follow the procedure:

For all current threads: let's say the thread is at the state $$$A$$$. For all edges from $$$A$$$ to some $$$B$$$ that have the character $$$S_i$$$, we will prepare to create a new thread at $$$B$$$ and delete the thread at $$$A$$$. After considering all current threads, first delete all of them and then create all the new ones we had prepared to create.

If at the end there is any thread at any accepting state, the automaton "accepts" the string. You can assume the deterministic version is the same, but each state should have exactly one outgoing edge for each letter (so simulating it is just traversing a graph).

The Problem

We want to solve the string matching problem: given two strings $$$S$$$ and $$$P$$$, find all substrings of $$$S$$$ that match the pattern $$$P$$$. There are other uses for the concepts shown here, but we'll focus on this one first.

A Simple Solution

There's a pretty simple NFA construction that solves this exact problem. We'll feed this automaton the characters of $$$S$$$ as input, and if at any point a thread is at the accepting state, we'll know there's a substring that matches $$$P$$$. Let the starting state have an edge to itself for every character of the alphabet (remember this is the alphabet of the automaton, not necessarily the English alphabet). This loop will create a thread at every input character and leave it there, at the starting node, ready to match the pattern when the other inputs come. Next, we'll make a path containing the characters of the pattern $$$P$$$ at every edge. Here's an example of an NFA that matches the pattern "abacaba":

Notice that the $$$Σ$$$ edge in the first node represents "an edge for every symbol of the alphabet", and that it includes the letter "a" in this case. Thus, if the automaton receives an "a", the thread in the first node splits into one for the second node and one that keeps looping on the starting node. When this split occurs, one of the threads will keep "walking" to the right while the symbols of the string are matching the forward edges, but if at any point they don't match, the thread "dies". Take a moment to appreciate how this simple NFA solves the matching problem.

An Example

Let's look at an automaton that matches the pattern "abaa". The nodes filled in red represent alive threads.

We'll input the string "abaab" and see how the threads behave. First, let's input the letter "a".

The thread we had before split into two, and now the one on the right will try to walk to the right as far as it can. Now we input the second character of our string, "b".

Nothing surprising here. Let's input "a".

Now there are 3 threads, look at them go! Now input another "a".

Notice that the thread that was on the second node didn't have any edge to follow, so it died, but then the first node split and another thread is now at the second state. Also, we have a filled accepting state, so there's a match with the pattern "abaa"! One last input, "b".

We already have a thread matching the "b" from "abaa", even if this first "a" overlaps with our first match. This kind of behaviour allows us to match overlapping patterns efficiently.

Running the Automaton

The naive way to run this automaton is to keep a set of threads and advance them individually. This is, however, not efficient at all. Imagine the pattern is something like "aaaaaa", and we match a string "aaaaaaaaaaaaaaaaa". At every iteration a new thread would be spawned and every other thread would advance, with no deaths. This gives us a time complexity of $$$O(|S| × |P|)$$$. We can do better by exploiting some properties.

How many states are reachable?

There is potential to do better than the naive simulation by analyzing what is called the "subset construction" of our NFA (think of all possible combinations (subsets) of threads that can be alive at the same time). Indeed, only $$$|P|+1$$$ subsets would be reachable in it! The proof is as follows: imagine we've input some string to the automaton and there's some set of alive threads. Let $$$u$$$ be the most advanced (closest to the right) thread alive -- we'll call it the "leader" thread --, and let $$$n$$$ be the number of forward edges (the ones that aren't the loop) it followed. There are no threads to the right of $$$u$$$, so we only need to consider the last $$$n$$$ symbols the automaton has seen, and there's only one length-n string possible because there's only one path the thread could have followed. Because of that, the alive threads to the left of $$$u$$$ are uniquely determined! In other words, if we know the leader, there's only one possible set of alive threads to the left of it. With this, it's possible to conclude that there's exactly one reachable subset in the subset construction for every leader state, which gives us $$$|P|+1$$$ states in total (since we are including the subset with only the starting thread).

An idea one could have now is: when simulating the automaton, what if we only keep track of the leader thread, instead of the entire alive subset? This is exactly what we'll do, but there's a problem: what if the leader dies? We need to know who will occupy his place. Before that, though, we'll need one more concept.

Left-set

It turns out that "there's only one possible set of alive threads to the left of the leader" does not apply exclusively to the leader. In fact, if we know some thread is alive, all of the threads to the left of it can be uniquely determined. The argument is very similar to the one shown before, here's a sketch: if a thread is alive in node $$$n$$$ ($$$0$$$-indexed), then there's one possible string of length $$$n$$$ that must have been fed to the automaton in the last $$$n$$$ steps, thus the threads in smaller positions must have come from this string.

Now we can finally know what to do in the case of a failed match.

Dealing with failure

Suppose we've built the automaton for "abababax" and fed "abababa" to it.

What would happen if we input the letter "b"? Well, the leader can't go forward, so it dies. The thread immediately to the left of the leader, however, can go forward, and thus becomes the new leader. We'll call this "thread immediately to the left of a thread" the "neighbor". This idea outlines a possible efficient way of simulating our NFA. We'll keep track of the position of the leader at every step. How? There are two cases:

1. The leader matches the input and goes forward. This case is easy, just increment the current leader position.
2. The leader fails to match and dies. Then, the neighbor of the leader (let him be at position $$$n0$$$) may or may not survive. If it does, the new leader is at $$$n0+1$$$. If it dies, then maybe the neighbor of this other thread (at $$$n1 \lt n0$$$) survives. If it does, the new leader is at $$$n1+1$$$. If it dies, then maybe their neighbor survives. You get the idea; in the worst case, we can always go all way back to the starting node, who always has an alive thread.

Then, if we could know the neighbor of a thread in $$$O(1)$$$, the entire matching process would take time $$$O(|S|)$$$. Yes, even if we walk through neighbors one by one as they die, the algorithm runs in linear time. To see why, consider that we spawn at most one thread per step, so the total number of dead threads is bounded by $$$|S|$$$. It's like pushing threads to a queue when they are spawned and popping the queue when they die.

Precalculating the Neighbor

When building our automaton, we'll precalculate an array neighbor, where neighbor[u] indicates the neighbor of $$$u$$$, in the case where $$$u$$$ is the leader. If we do that, we'll be able to simulate our automaton as described in "Dealing with failure" in $$$O(|S|)$$$!

It turns out precalculating the neighbor is very similar to what we've seen in "Dealing with failure". Let's compute the neighbor array from left to right. Suppose we've already computed the result for the first $$$k$$$ vertices. How do we compute it for the $$$k+1$$$-th? The only way the leader could move from $$$k$$$ to $$$k+1$$$ is to go through the edge between them, right? So it means we got $$$P_k$$$ as input ($$$0$$$-indexed). If neighbor[k] has an edge with the letter $$$P_k$$$, then neighbor[k+1] = neighbor[k]+1. If not, let's check the edge from neighbor[neighbor[k]]], and so on, until we succeed or reach the start state. You can use the same argument from the previous section to prove that this is $$$O(|P|)$$$.

In fact, this is the same as calculating who is the new leader when the leader is neighbor[k] and we receive $$$P_k$$$ as input!

Implementation

I'll take this moment to remember about LeoRiether's amazing KMP simulator. It is very useful to simulate some examples.

Let's get to the actual code. We have come to the conclusion that the only thing that we need is to calculate the new leader based on the previous leader and the input character, which depends whether the leader's edge matches the input or not. We can implement the exact logic we've been discussing:

struct KMP {
	string P;
	int n; // n = |P|
	vector<int> neighbor;
	
	KMP(string& p){
		P = p;
		n = (int)P.size();
		neighbor.resize(n+1);
		neighbor[1] = 0; //starting node is always alive
		for(int k = 1; k < n; k++)
			neighbor[k+1] = next_leader(neighbor[k], P[k]);
	}
	
	bool match(int state, char c){
		return state < n and P[state] == c;
	}
	
	int next_leader(int leader, char input){
		if (leader == 0)return P[0] == input; 
		// either advances to 1 or remains in start
		if (match(leader, input))return leader+1;
		else return next_leader(neighbor[leader], input);
	}
};

Whenever the leader is at the position $$$|P|$$$, we have found a match:

int matches(string P, string S){
    KMP kmp(P);
    int count = 0, state = 0;
    for(char c : S){
        state = kmp.next_leader(state, c);
        if (state == (int)P.size())count++;
    }
    return count;
}

I personally prefer a more reduced implementation:

struct KMP {
	string P; int n; vector<int> nb;
	
	KMP(string& p) : P(p), n((int)P.size()), nb(n+1) {
		for(int k = 1; k < n; k++) nb[k+1] = nxt(nb[k], P[k]);
	}
	
	int nxt(int i, char c){
		for(; i; i = nb[i])if (i < n and P[i]==c)return i+1;
		return P[0]==c;
	}
};

LeoRiether's can be found here.

You can test your implementation here.

Prefix Function

The currently most popular interpretation for the KMP algorithm is as a Prefix Function: for each prefix $$$p$$$ of a string $$$S$$$, it returns the length of the second largest prefix of $$$p$$$ that is also a suffix of it (the first largest is, of course, $$$p$$$ itself).

This is equivalent to, when the leader thread is at the state $$$|p|$$$, the position of the second largest alive thread, which is exactly our neighbor array. You can see this clearly if you think about what happens when we feed the characters of $$$P$$$ to the automaton we have just built.

The KMP Automaton

We have seen how to solve the string matching problem in $$$O(|P| + |S|)$$$. However, in some problems (like this one), we may want to store something like: for all possible leaders and input characters, what would be the new leader. This means to construct an explicit DFA that is equivalent to the NFA we were simulating earlier. When people talk about the "KMP Automaton", this is usually what they mean.

This construction can be made using dynamic programming. If the result has been calculated for the first $$$k$$$ states, for the $$$k+1$$$-th we iterate each character $$$c$$$ of the alphabet. Then, we have two possibilities:

1. If $$$P_k = c$$$: the new leader is $$$k+1$$$.
2. If not, the answer is the same as the already calculated at the state neighbor[k+1].

You can add the following to the KMP implementation to achieve this (considering the alphabet from $$$a$$$ to $$$z$$$):

    vector<vector<int>> dfa(n+1, vector<int>(26));
    void build_dfa(){
        dfa[0][P[0]] = 1; //only way to advance at 0
        for(int k = 1; k <= n; k++)
            for(int c = 0; c < 26; c++)
                if (k < n and P[k] == 'a'+c) dfa[k][c] = k+1;
                else dfa[k][c] = dfa[neighbor[k]][c];
    }

Conclusion

I'd like to thank LeoRiether again for letting me complete his work and share the final result with the Codeforces community. Also, thanks to duduFreire and felipe_massa for the excellent review on this blog.

I hope you liked the ideas presented as much as I did!