Prefix function

When we search inside a string, there are certain questions that come to mind. Does a string have a pattern? And if it has some recurrent parts, how many of them are there? We need to know how to answer them because they can direct our actions: for example, if a part of a string repeats itself, we can easily compress this string, and so on.

In this topic, we will introduce a unique structure called prefix function that will allow us to investigate the borders of substrings. Then, we will develop an approach to find the prefix function using its definition.

Border and its length

Recall that a border of a string $s$ is a proper prefix of $s$ that is also a suffix of that string. It is worth noting that a string usually has more than one border and it is completely normal for borders to intersect themselves. Let's escape from abstraction by taking a look at a couple of examples:

An array of border lengths

We are ready to define our main tool now, the prefix function. First of all, let's grasp the main idea:

1. A prefix function is an array specific to a string. So, let's consider a string first: $MAMMAMIA$.

2. Our computations will yield an array of numbers, the length of which corresponds to the length of the string. Specifically, for our scenario, the prefix function will produce an array with a length of $8$.

3. Moving forward, we'll examine particular substrings from our provided string. For instance, $M, MAM, AMM, AMI, MAMMA,$ and so forth are all substrings of $MAMMAMIA$. Nonetheless, our focus will be solely on those substrings that initiate from the start of our provided string, in other words, all the prefixes. This includes $M, MA, MAM, MAMM, MAMMA, MAMMAM, MAMMAMI,$ and $MAMMAMIA$.

4. Now we will examine the borders of those substrings one by one.

   1. Starting with the first substring $M$, doesn't have a border, as it lacks a proper prefix. By definition, a proper suffix or prefix cannot equal the string itself.

   2. Next, the substring $MA$ also doesn't have a border because it doesn't have a proper prefix that is also a suffix.

   3. The substring $MAM$ does have a border, as $M$ serves as both the prefix and suffix. Consequently, it has a border length of $1$.

   4. The substring $MAMM$ also has a border length of $1$.

   5. $MAMMA$ has $MA$ as its border, resulting in a border length of $2$.

   6. $MAMMAM$ has a border length of $3$.

   7. $MAMMAMI$ doesn't have a border.

   8. Finally, $MAMMAMIA$ also lacks a border.

5. The prefix function for $MAMMAMIA$ is the array that consists of the lengths of the borders for those substrings, that is, $[0, 0, 1, 1, 2, 3, 0, 0]$.

Definition of the prefix function

If the example above is clear now, let's move on to the official definition. Given a string $s$ of length $n$. One can define the prefix function of $s$ as an array $p$ of length $n$, where $p[i]$ is the length of the longest border of the substring $s[1, i]$. It is obvious that $p[1] = 0$, since a string of length $1$ can't have nonempty proper prefixes.

In order to get a better understanding of this notion, let's calculate the prefix function of some strings. Take the string $s=ABACABB$ and another string $w=AAAABA$ . First of all, we will examine the prefixes of those two strings and find the longest borders for each one of them:

Following the definition, after some observations (see the picture on the left), we conclude that the prefix function of the first string is $[0,0,1,0,1,2,0]$. For example, $p[6] = 2$, because the longest border of the substring $s[1,6] = ABACAB$ is $AB$, whose length is $2.$

String $w=AAAABA$, and it is a bit trickier! Keep in mind that a border is a proper prefix-suffix and it might intersect itself. Here, we conclude that $p=[0,1,2,3,0,1]$ as in the picture on the right.

An algorithm from the definition

So, how did we calculate the prefix functions above? Directly by definition – a method that is known as the naive approach. Here is the pseudocode for this approach:

function compute_prefix_function(s)
    n = length(s)
    p = array[1, n]
    p[1] = 0

    for i in [2, n]:
        p[i] = 0
        for j in [1, i-1]:
            if s[1, j] = s[i-j+1, i]:
                p[i]=j  

    return p

Here for each one of $n$ prefixes $s[1,i]$ of the initial string, we find the longest border by comparing the prefixes and suffixes of every length to detect the borders, and then we choose the longest amongst them. Every steps are according to our official definition of the prefix function. Now, let's analyze its performance.

Complexity

There are $n$ substrings in our string $s$ . For each one, it takes $O(n^2)$ time to find the longest border since we compare two strings in linear time for every possible length. Hence the general time complexity is $O(n^2*n)$ i.e. $O(n^3)$ which is too long.

In practice, strings can have enormous lengths, so we need to come up with a much more efficient algorithm. In order to accomplish this, we will utilize the characteristics of borders in a future topic.

Conclusion

In this topic, we introduced a new structure of string called the prefix function and developed a naive algorithm to find it. Here are the steps of our algorithm:

1. Create an empty array $p$ of length $|s|$.

2. For each $p[i]$ find the length of the largest border of the prefix $s[1,i]$.

Understanding the prefix function is crucial for developing advanced string algorithms. Therefore, it is important to properly comprehend this topic. Later on, we will explore a more efficient algorithm with linear time complexity to determine the prefix function of a string.