给定一个长度为的字符串，其前缀函数被定义为一个长度为的数组。其中的定义是：
简单来说就是，子串最长的相等的真前缀与真后缀的长度。
用数学语言描述如下：
特别地，规定。
举例来说，对于字符串abcabcd，
，因为a没有真前缀和真后缀，根据规定为0
，因为ab无相等的真前缀和真后缀
，因为abc无相等的真前缀和真后缀
，因为abca只有一对相等的真前缀和真后缀：a，长度为1
，因为abcab相等的真前缀和真后缀只有ab，长度为2
，因为abcabc相等的真前缀和真后缀只有abc，长度为3
，因为abcabcd无相等的真前缀和真后缀
同理可以计算字符串aabaaab的前缀函数为。
一个直接按照定义计算前缀函数的算法流程：
具体实现如下：
第一个重要的观察是相邻的前缀函数值至多增加。
参照下图所示，只需如此考虑：当取一个尽可能大的时，必然要求新增的也与之对应的字符匹配，即,此时。
所以当移动到下一个位置时，前缀函数的值要么增加一，要么维持不变，要么减少。
此时的改进的算法为：
1234567891011vector
而由于存在j=pi[i-1]+1（pi[0]=0）对于最大字符串比较次数的限制，可以看出每次只有在最好情况才会为字符串比较次数的上限积累1，而每次超过一次的字符串比较消耗的是之后次数的增长空间。
由此我们可以得出字符串比较次数最多的一种情况：至少1次字符串比较次数的消耗和最多n-2次比较次数的积累，此时字符串比较次数为n-1+n-2=2n-3。
可见经过此次优化，计算前缀函数只需要进行次字符串比较，总复杂度降为了。
在第一个优化中，我们讨论了计算时的最好情况：，此时。现在让我们沿着这个思路走得更远一点：讨论当时如何跳转。
失配时，我们希望找到对于子串，仅次于的第二长度，使得在位置的前缀性质仍得以保持，也即：
如果我们找到了这样的长度，那么仅需要再次比较和。如果它们相等，那么就有。否则，我们需要找到子串仅次于的第二长度，使得前缀性质得以保持，如此反复，直到。如果，则。
观察上图可以发现，因为，所以对于的第二长度，有这样的性质：
也就是说等价于子串的前缀函数值，即。同理，次于的第二长度等价于的前缀函数值，
显然我们可以得到一个关于的状态转移方程：0)"src=data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7>
所以最终我们可以构建一个不需要进行任何字符串比较，并且只进行次操作的算法。
而且该算法的实现出人意料的短且直观：
1234567891011vector
该任务是前缀函数的一个典型应用。
给定一个文本和一个字符串，我们尝试找到并展示在中的所有出现（occurrence）。
为了简便起见，我们用表示字符串的长度，用表示文本的长度。
我们构造一个字符串，其中为一个既不出现在中也不出现在中的分隔符。接下来计算该字符串的前缀函数。现在考虑该前缀函数除去最开始个值（即属于字符串和分隔符的函数值）后其余函数值的意义。根据定义，为右端点在且同时为一个前缀的最长真子串的长度，具体到我们的这种情况下，其值为与的前缀相同且右端点位于的最长子串的长度。由于分隔符的存在，该长度不可能超过。而如果等式成立，则意味着完整出现在该位置（即其右端点位于位置）。注意该位置的下标是对字符串而言的。
因此如果在某一位置有成立，则字符串在字符串的处出现。
正如在前缀函数的计算中已经提到的那样，如果我们知道前缀函数的值永远不超过一特定值，那么我们不需要存储整个字符串以及整个前缀函数，而只需要二者开头的一部分。在我们这种情况下这意味着只需要存储字符串以及相应的前缀函数值即可。我们可以一次读入字符串的一个字符并计算当前位置的前缀函数值。
对字符串和，若长度为的前缀和长度为的后缀相等，就称长度为的前缀是的border。
由有长度为的border可以推导出是的周期。
在该节我们将同时讨论两个问题。给定一个长度为的字符串，在问题的第一个变种中我们希望统计每个前缀在同一个字符串的出现次数，在问题的第二个变种中我们希望统计每个前缀在另一个给定字符串中的出现次数。
首先让我们来解决第一个问题。考虑位置的前缀函数值。根据定义，其意味着字符串一个长度为的前缀在位置出现并以为右端点，同时不存在一个更长的前缀满足前述定义。与此同时，更短的前缀可能以该位置为右端点。容易看出，我们遇到了在计算前缀函数时已经回答过的问题：给定一个长度为的前缀，同时其也是一个右端点位于的后缀，下一个更小的前缀长度是多少？该长度的前缀需同时也是一个右端点为的后缀。因此以位置为右端点，有长度为的前缀，有长度为的前缀，有长度为的前缀，等等，直到长度变为。故而我们可以通过下述方式计算答案。
给定一个长度为的字符串，我们希望计算其本质不同子串的数目。
我们将迭代的解决该问题。换句话说，在知道了当前的本质不同子串的数目的情况下，我们要找出一种在末尾添加一个字符后重新计算该数目的方法。
令为当前的本质不同子串数量。我们添加一个新的字符至。显然，会有一些新的子串以字符结尾。我们希望对这些以该字符结尾且我们之前未曾遇到的子串计数。
构造字符串并将其反转得到字符串。现在我们的任务变为计算有多少的前缀未在的其余任何地方出现。如果我们计算了的前缀函数最大值，那么最长的出现在中的前缀其长度为。自然的，所有更短的前缀也出现了。
因此，当添加了一个新字符后新出现的子串数目为。
值得注意的是，我们也可以重新计算在头部添加一个字符，或者从尾或者头移除一个字符时的本质不同子串数目。
给定一个长度为的字符串，我们希望找到其最短的「压缩」表示，也即我们希望寻找一个最短的字符串，使得可以被的一份或多份拷贝的拼接表示。
显然，我们只需要找到的长度即可。知道了该长度，该问题的答案即为长度为该值的的前缀。
让我们计算的前缀函数。通过使用该函数的最后一个值，我们定义值。我们将证明，如果整除，那么就是答案，否则不存在一个有效的压缩，故答案为。
假定可被整除。那么字符串可被划分为长度为的若干块。根据前缀函数的定义，该字符串长度为的前缀等于其后缀。但是这意味着最后一个块同倒数第二个块相等，并且倒数第二个块同倒数第三个块相等，等等。作为其结果，所有块都是相等的，因此我们可以将字符串压缩至长度。
诚然，我们仍需证明该值为最优解。实际上，如果有一个比更小的压缩表示，那么前缀函数的最后一个值必定比要大。因此就是答案。
根据扩展欧几里得算法我们可以得到一组和使得。通过与等式适当叠加我们可以得到一组0"src=data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7>和使得。这意味着通过不断应用前述方程组中的方程我们可以得到新的方程组。
由于整除，这意味着是的一个周期。又因为n-p"src=data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7>，故有，所以是一个比更小的的周期。因此字符串有一个长度为的压缩表示，同的最小性矛盾。
综上所述，不存在一个长度小于的压缩表示，因此答案为。
让我们重新回到通过一个分隔符将两个字符串拼接的新字符串。对于字符串和我们计算的前缀函数。显然，因为是一个分隔符，前缀函数值永远不会超过。因此我们只需要存储字符串和其对应的前缀函数值，之后就可以动态计算对于之后所有字符的前缀函数值：
实际上在这种情况下，知道的下一个字符以及之前位置的前缀函数值便足以计算下一个位置的前缀函数值，而不需要用到任何其它的字符和对应的前缀函数值。
换句话说，我们可以构造一个自动机（一个有限状态机）：其状态为当前的前缀函数值，而从一个状态到另一个状态的转移则由下一个字符确定。
因此，即使没有字符串，我们同样可以应用构造转移表的算法构造一个转移表：
该自动机在什么时候有用呢？首先，记得大部分时候我们为了一个目的使用字符串的前缀函数：寻找字符串在字符串中的所有出现。
因此使用该自动机的最直接的好处是加速计算字符串的前缀函数。
通过构建的自动机，我们不再需要存储字符串以及其对应的前缀函数值。所有转移已经在表中计算过了。
但除此以外，还有第二个不那么直接的应用。我们可以在字符串是某些通过一些规则构造的巨型字符串时，使用该自动机加速计算。Gray字符串，或者一个由一些短的输入串的递归组合所构造的字符串都是这种例子。
出于完整性考虑，我们来解决这样一个问题：给定一个数，以及一个长度的字符串，我们需要计算在第个Gray字符串中的出现次数。回想起Gray字符串以下述方式定义：
由于其天文数字般的长度，在这种情况下即使构造字符串都是不可能的：第个Gray字符串有个字符。然而我们可以在仅仅知道开头若干前缀函数值的情况下，有效计算该字符串末尾的前缀函数值。
除了自动机之外，我们同时需要计算值：在从状态开始处理后的自动机的状态，以及值：当从状态开始处理后，在中的出现次数。实际上为在执行操作时前缀函数取值为的次数。易得问题的答案为。
我们该如何计算这些值呢？首先根据定义，初始条件为以及。之后所有值可以通过先前的值以及使用自动机计算得到。为了对某个计算相应值，回想起字符串由，字母表中第个字符，以及三者拼接而成。因此自动机会途径下列状态：
的值同样可被简单计算。
其中当其中表达式取值为真时值为，否则为。综上，我们已经可以解决关于Gray字符串的问题，以及一大类与之类似的问题。举例来说，应用同样的方法可以解决下列问题：给定一个字符串以及一些模式，其中每个模式以下列方式给出：该模式由普通字符组成，当中可能以的形式递归插入先前的字符串，也即在该位置我们必须插入字符串次。以下是这些模式的一个例子：
递归代入会使字符串长度爆炸式增长，他们的长度甚至可以达到的数量级。而我们必须找到字符串在每个字符串中的出现次数。
该问题同样可通过构造前缀函数的自动机解决。同之前一样，我们利用先前计算过的结果对每个模式计算其转移然后相应统计答案即可。