串的基本概念

复习定位

串的匹配是计算机中的基础操作——文本编辑器搜索功能、grep命令、DNA序列比对都用到字符串匹配算法。朴素匹配复杂度O(m×n)——在文本和模式串长时效率极低。KMP算法利用模式串的自身前缀信息(next数组)——在不回溯主串指针的情况下高效匹配——将复杂度降到O(m+n)。

串的定义与存储

串是由0个或多个字符组成的有限序列——记为S = "a₁a₂...aₙ"——n为串的长度(字符个数)——n=0时称为空串。空格串(" ")是由空格字符组成的串——长度>0——和空串不同。

串的顺序存储——用字符数组存储字符序列——可随机访问任意字符。
串的链式存储——每个结点存储多个字符(如4个字符)——减少指针占用。

KMP算法

朴素串匹配的过程——主串指针i在每次失配时回退到i-(j-1)+1(即已匹配的第一个字符的后一个字符)然后重新与模式串的开头字符比较——这导致了大量的重复比较。

KMP的核心改良——主串指针永不回退——当模式串的第j个字符与主串的第i个字符失配时——i不会回退——而是利用next数组跳过模式串的前几个字符。

next数组——对于模式串P——next[j]表示在下标j处的字符失配时——模式串下一轮应跳转到哪个下标继续与主串比较(即最大的k使得P[0..k-1]==P[j-k..j-1])——实际上是模式串以j结尾的子串的最长相等前后缀的长度。

模式串P = "ABABAC"的next数组:
P  A B A B A C
j  0 1 2 3 4 5
next[0] = -1 (特殊——移动模式串)
next[1] = 0  (前缀""长度0)
next[2] = 0  ("AB"的前缀"A"和后缀"B"不相等——长度为0)
next[3] = 1  ("ABA"的前缀"A"=后缀"A"——长度为1)
next[4] = 2  ("ABAB"→"AB"="AB"长度2)
next[5] = 3  ("ABABA"→"ABA"="ABA"长度3)

KMP匹配过程——主串i=0、模式串j=0——比较s[i]和p[j]——相等则i++,j++；不相等则j=next[j]——如果j==-1则i++,j++。

KMP的改进——nextval数组

原始的next可能存在一些无效的跳转。例如P="aaaaaaab"——next数组在生产中遇到了一系列的a匹配失败后——仍需要一步一步跳转。nextval对next进行了优化——在失配时检查如果P[next[j]] == P[j]——则继续递推——避免连续相同字符的无效比较。

复习检查

1. 朴素串匹配的时间复杂度为什么是O(m×n)——最坏情况下——模式串的每个字符都与主串的每个字符比较一次——发生在模式串很长且大部分字符都匹配——只在最后一位发现不匹配(如主串=aaaaa...aab、模式串=aaa……ab)——每次匹配到模式串尾部才失配——主串指针回退一位再次匹配——总比较数约O(m×n)。

2. KMP为什么将复杂度降为O(m+n)——主串指针永不回退——每个字符最多被比较一次——next数组的构造本身O(m)——因此总的比较次数是m+n。

3. next数组的"最长相等前后缀"是什么意思——前缀是包括第一个字符但不包括最后一个字符的子串——后缀是包括最后一个字符但不包括第一个字符的子串——最长相等前后缀意味着在子串中找到一个最长的前缀和后缀相等。

4. KMP在匹配过程中——主串指针i如何避免回退——当模式串第j个字符失配时——主串i不变、模式串j跳到next[j]的位置——只有在j回退到-1时——i才前进一位——主串指针只前进不后退。

5. nextval数组的优化思路——当p[j]==p[next[j]]时——下次跳到next[j]还是会失配——所以要继续递推到下一个不同的字符位置——避免重复比较相同字符。