字符串的相关概念

字符串是由字符连接而成的序列，没有字符的称为空串。子串指字符串中连续的一部分，而子序列指按顺序挑选出字符组成的字符串，可以不连续。

包括一个字符串最开头字符的字串称为字符串的前缀，包括一个字符串末尾字符的字串称为字符串的后缀；真前缀指除了字符串本身的前缀，真后缀同理。

两个字符串可以比较顺序，称为字典序。逐位比较字符，若不相同，对应字符靠前的字符串的字典序就靠前。另外，若字符串 $S_1$ 是另一个字符串 $S_2$ 的真前缀，则 $S_1$ 字典序靠前。

字符串反过来写称为字符串的逆序。若一个字符串逆序等于它本身，称为回文字符串。

KMP 字符串匹配

前缀函数及其计算

概念与初始实现

现定义前缀函数为一个长度为 $n$ 的数组 $\pi$，$\pi[i]$ 的含义是：字串 $s[0\dots i]$ 最长的相等的真前缀与真后缀的长度。以字符串 abcabcd 为例：

• $\pi[0]=0$，因为 a 没有真前缀、真后缀
• $\pi[1]=\pi[2]=0$，因为 ab，abc 没有相等的真前缀、真后缀
• $\pi[3]=1$，因为 abca 有相等的长度为 $1$ 的真前缀、真后缀 a
• $\pi[4]=2$，因为 abcab 有相等的长度为 $2$ 的真前缀、真后缀 ab
• $\pi[5]=3$，因为 abcabc 有相等的长度为 $3$ 的真前缀、真后缀 abc
• $\pi[6]=0$，因为 abcabcd 没有相等的真前缀、真后缀

得到前缀函数为 $[0,0,0,1,2,3,0]$.

直接按照顺序计算 $\pi[1\dots n-1]$，每次从最长的真前缀长度 $j=i$ 开始枚举，直到找到匹配的，则 $\pi[i]=j$，否则 $j$ 自减。若 $j=0$ 仍无匹配，$\pi[i]=0$，继续往后。