给两个字符串 S1 和 S2问 S1 里有没有 S2有的话返回它出现的最左位置没有就返回 -1。这个问题叫字符串匹配。最直接的做法是把 S1 的每个位置都当成起点试一遍。拿 S1 “ABCD”、S2 “CD” 来说从 0 位置开始A 对 C 对不上换 1 位置B 对 C 还是对不上换 2 位置这次 C 对 C、D 对 D 都对上了返回 2。要是 S2 是 “CDE”整个 S1 里找不出这一段返回 -1。这个做法好懂代价是慢。每换一个位置S2 都得从 0 开始重新比一遍前面那趟配出来的结果帮不上后面那趟。S1 有 n 个字符S2 有 m 个字符最坏情况下从每个位置开始都要往后比 m 次两边一乘就是 O(n × m)。举个极端的例子S1 是一长串 aS2 是 “aaf”。每个 a 当起点时都要先对上两个 a再在第三个字符上对不上然后换下一个 a把 S2 的前两个 a 重新对一遍。KMP 算法换了个思路它能把时间压到 O(n m)靠的是 S1 的比对位置只往前从不回头。代价是先把 S2 加工一遍加工出来的结果叫 next 数组。这篇讲两件事next 数组长什么样拿着它匹配时两个比对位置怎么走。它自己怎么算出来留到下一篇。接下来都用这两个串S2 “AABAABCAABAABT”S1 “AABAABCAABAABXA”。next 数组只看 S2算它的时候用的全是 S2 自己的字符跟 S1 没关系。S2 的每个位置对应一个数这个数说的是它前面那段字符串里前缀和后缀相等的最大长度。前缀从头开始取后缀到末尾结束。这里有两个地方容易搞混1.算的是这个位置前面那段字符串不含这个位置上的字符。2.前缀和后缀都不能取到整段。取到整段就是拿整段去对整段前缀和后缀必然相等算出来的数就等于整段的长度但这样的相等说明不了任何东西。比如 S2 “AABAABCAABAABT” 里的位置 6这个位置上的字符是 C它前面那段字符串就是 AABAAB。这里假设 S2 至少有一个字符先讲第 0 个和第 1 个位置。第 0 个位置固定是 -1。它前面一个字符都没有这个长度不存在按约定写成 -1。第 1 个位置固定是 0它前面只有一个字符又不能取到整段只能拿空的前缀去对空的后缀长度是 0。不管 S2 长什么样这两个位置的值都是定死的。把 S2 取成 “AABAABCAABAABT”从头到尾算一遍位置前面那段字符串相等的最长前缀和后缀next 值0没有没有-11A空02AAA13AAB空04AABAA15AABAAAA26AABAABAAB37AABAABC空08AABAABCAA19AABAABCAAAA210AABAABCAABAAB311AABAABCAABAAABA412AABAABCAABAAAABAA513AABAABCAABAABAABAAB6挑几个位置核对一遍。位置 2 前面是 “AA”前一个 A 和后一个 A 相等取 1。位置 6 前面是 “AABAAB”前三个字符和后三个字符都是 “AAB”取 3。位置 7 前面是 “AABAABC”从头取一段、从尾取一段怎么取都对不上这个位置就是 0。位置 13 前面是 “AABAABCAABAAB”前缀和后缀里最长的一对是 “AABAAB”取 6。这张表就是 S2 的 next 数组14 个位置14 个数。还有一种位置它的前缀和后缀会重叠这里提一下比如某个字符前面是 “AAAAA”前缀取 4 个 A、后缀取 4 个 A这两段有 3 个字符是共用的两边照样相等这个位置的 next 值就是 4。刚才那个 S2 里没有这种位置表里 14 个数前缀和后缀没有一处叠在一起看表和看图都更方便。拿到 next 数组两个比对位置怎么走匹配还是从两个字符串的 0 位置开始S1 的 0 位置对着 S2 的 0位置字符相等就一起往后走。走到对不上的时候S1 的比对位置停住不动S2 的比对位置退到它刚才那个位置的 next 值所在的位置上接着往下比。拿 S1 和这个 S2 走一遍。两个串从各自的 0 位置开始一路都对得上一直对到 S1 的 13 位置和 S2 的 13 位置这里对不上了。13 位置的 next 值是 6于是 S2 的比对位置退到 6S1 的 13 位置不动让这两个位置接着比。S1中验证的起点变成 S1 的比对位置减去 S2 的比对位置即 13 减 6 得 7。这一退的含义就是 S2 不再从 S1 的 1 位置开始比对改为从 S1 的 7 位置开始比对。接下来要验的是从S1的 7 位置起把 S2 配出来。S1 的 13 位置对 S2 的 6 位置还是对不上6 位置的 next 值是 3S2 退到 3 位置S1中验证的起点变成 10 位置。S1 的 13 位置对 S2 的 3 位置依然对不上3 位置的 next 值是 0S2 退到 0 位置S1中验证的起点变成 13 位置。S1 的 13 位置对 S2 的 0 位置还是对不上0 位置的 next 值是 -1。这个 -1 说的是 S2 已经退无可退没有位置可退了。代码见到这个 -1不把 S2 的比对位置真改成 -1而是让 S1 换下一个位置从 14 位置重新对上 S2 的 0 位置。把整场匹配的几步列出来走到哪一步S1 的比对位置S2 的比对位置S1中验证的起点还没开始000一路配到对不上13130第一次退1367第二次退13310第三次退13013退不动换起点14014整个过程可以收成一句相等就一起往前不相等就把 S2 的比对位置回退到 next 数组元素的值对应的位置S2 退无可退时S1 的比对位置换下一个位置S2 留在 0 位置。S1 的 1 到 6 和 7 到 12 都不用再和 S2 比一遍S1 从 7 位置开始验证的时候S1 的 7 到 12 这 6 个字符没有重新对一遍直接拿 S1 的 13 位置去对 S2 的 6 位置。敢省掉这一步凭的是 next 值自己的定义。S2 的 13 位置的 next 值是 6意思是 S2 里 0 到 5 这一段和 7 到 12 这一段字符完全一样而且找不到比 6 更长的、相等的前缀和后缀。再补一条已知事实刚才是一路从 0 配到 13 位置才对不上的所以 S1 的 7 到 12 这一段和 S2 的 7 到 12 这一段字符也一样。S2 里 0 到 5 这一段和 S1 的 7 到 12 这一段都等于 S2 的 7 到 12所以它们彼此也相等。也就是说S1 的位置 7 到 12 和 S2 的位置 0 到 5 的字符完全一致。S2 对齐到 S1 的 7 位置之后S1 的 1 到 6 这几个起点也可以直接跳过。因为这几个起点配不出整个 S2。只要反过来推一遍就清楚了。假设里面真有一个起点从它开始能把整个 S2 完整对上。既然能对上S1 从这个起点到 12 位置的一段就得和 S2 的开头一段完全相等。起点还必须在 1 到 6 之间那这一段最少有 7 个字符。S1 的 0 到 12 又是一路配到 13 位置才对不上的所以从起点到 12 位置的同一段也等于 S2 里同样位置的一段。两个说法指的是 S1 里同一段字符于是 S2 的开头一段和 S2 靠后的同样长的一段字符完全一样。开头那段从 0 位置开始是前缀靠后那段一直延伸到 12 位置是后缀。这一对相等的前缀和后缀长度就是起点到 12 位置那段的长度最少 7 个字符比 6 长。可 next 值 6 指的就是最长只到 6。这个数是拿 S2 自己的字符算出来的不会出错。出错的就是刚才那个假设1 到 6 这几个起点都配不出整个 S2直接跳过去没有问题。next 值的二义性6 是 0 到 5 这六个字符的长度而 0 到 5 后面紧跟着的那个字符位置正好也是 6。所以S2退到 6退的是长度也是那段前缀后面那个字符所在的位置。两个说法指着同一格写代码的时候直接用这个数当下标就行。主流程就三个分支不相等的时候S2 的比对位置往回退不会漏掉任何还能配上整个 S2 的机会S1 上跳过的那几个起点本来就不可能配上。这两件事合起来整个匹配过程只剩三种情况。1.两个位置的字符相等两个比对位置一起往后走。2.不相等但 S2 还能退S2 的比对位置退到 next 值上S1 不动。3.不相等S2 退到 0 位置还是对不上S1 换下一个位置重新开始S2 还在 0 位置。intx0;// S1 上正在比对的位置inty0;// S2 上正在比对的位置while(xnym){if(s1.charAt(x)s2.charAt(y)){x;// 相等两个位置一起往后y;}elseif(next[y]-1){// S2 退无可退S1 换下一个起点x;}else{ynext[y];// S1 不动S2 退到 next 值上}}returnym?x-m:-1;// S2 走完说明配上了起点是 x - m代码大白话x和y挨着两边的字符对上了一起往后挪一个位置next[y] -1时单独xS2 已经退到 0 位置还是对不上换 S1 的下一个起点y next[y]S1 不动S2 退到它自己记着的那个位置y mS2 整个配完了说明找到了x - m比对位置往前推 m 个位置就是这段匹配的起点循环走完而y没到 mS1 走到底还没配上返回 -1跳出循环的判据落在 y 上。如果它走到 m说明 S2 从头到尾都配上了这时候 S1 的比对位置往后推 m 个位置就是答案。如果它是被 x 走到底打断的说明 S1 里没有 S2。收尾S1 的比对位置从头到尾只往前没有往回退过这就是 next 数组在匹配里做的事。next 数组自己怎么算出来以及这一路的来回为什么总共只花 O(n m)这两件事放在下一篇。
【KMP算法-上篇】匹配失败之后，KMP 凭什么敢一次跳过一大段
给两个字符串 S1 和 S2问 S1 里有没有 S2有的话返回它出现的最左位置没有就返回 -1。这个问题叫字符串匹配。最直接的做法是把 S1 的每个位置都当成起点试一遍。拿 S1 “ABCD”、S2 “CD” 来说从 0 位置开始A 对 C 对不上换 1 位置B 对 C 还是对不上换 2 位置这次 C 对 C、D 对 D 都对上了返回 2。要是 S2 是 “CDE”整个 S1 里找不出这一段返回 -1。这个做法好懂代价是慢。每换一个位置S2 都得从 0 开始重新比一遍前面那趟配出来的结果帮不上后面那趟。S1 有 n 个字符S2 有 m 个字符最坏情况下从每个位置开始都要往后比 m 次两边一乘就是 O(n × m)。举个极端的例子S1 是一长串 aS2 是 “aaf”。每个 a 当起点时都要先对上两个 a再在第三个字符上对不上然后换下一个 a把 S2 的前两个 a 重新对一遍。KMP 算法换了个思路它能把时间压到 O(n m)靠的是 S1 的比对位置只往前从不回头。代价是先把 S2 加工一遍加工出来的结果叫 next 数组。这篇讲两件事next 数组长什么样拿着它匹配时两个比对位置怎么走。它自己怎么算出来留到下一篇。接下来都用这两个串S2 “AABAABCAABAABT”S1 “AABAABCAABAABXA”。next 数组只看 S2算它的时候用的全是 S2 自己的字符跟 S1 没关系。S2 的每个位置对应一个数这个数说的是它前面那段字符串里前缀和后缀相等的最大长度。前缀从头开始取后缀到末尾结束。这里有两个地方容易搞混1.算的是这个位置前面那段字符串不含这个位置上的字符。2.前缀和后缀都不能取到整段。取到整段就是拿整段去对整段前缀和后缀必然相等算出来的数就等于整段的长度但这样的相等说明不了任何东西。比如 S2 “AABAABCAABAABT” 里的位置 6这个位置上的字符是 C它前面那段字符串就是 AABAAB。这里假设 S2 至少有一个字符先讲第 0 个和第 1 个位置。第 0 个位置固定是 -1。它前面一个字符都没有这个长度不存在按约定写成 -1。第 1 个位置固定是 0它前面只有一个字符又不能取到整段只能拿空的前缀去对空的后缀长度是 0。不管 S2 长什么样这两个位置的值都是定死的。把 S2 取成 “AABAABCAABAABT”从头到尾算一遍位置前面那段字符串相等的最长前缀和后缀next 值0没有没有-11A空02AAA13AAB空04AABAA15AABAAAA26AABAABAAB37AABAABC空08AABAABCAA19AABAABCAAAA210AABAABCAABAAB311AABAABCAABAAABA412AABAABCAABAAAABAA513AABAABCAABAABAABAAB6挑几个位置核对一遍。位置 2 前面是 “AA”前一个 A 和后一个 A 相等取 1。位置 6 前面是 “AABAAB”前三个字符和后三个字符都是 “AAB”取 3。位置 7 前面是 “AABAABC”从头取一段、从尾取一段怎么取都对不上这个位置就是 0。位置 13 前面是 “AABAABCAABAAB”前缀和后缀里最长的一对是 “AABAAB”取 6。这张表就是 S2 的 next 数组14 个位置14 个数。还有一种位置它的前缀和后缀会重叠这里提一下比如某个字符前面是 “AAAAA”前缀取 4 个 A、后缀取 4 个 A这两段有 3 个字符是共用的两边照样相等这个位置的 next 值就是 4。刚才那个 S2 里没有这种位置表里 14 个数前缀和后缀没有一处叠在一起看表和看图都更方便。拿到 next 数组两个比对位置怎么走匹配还是从两个字符串的 0 位置开始S1 的 0 位置对着 S2 的 0位置字符相等就一起往后走。走到对不上的时候S1 的比对位置停住不动S2 的比对位置退到它刚才那个位置的 next 值所在的位置上接着往下比。拿 S1 和这个 S2 走一遍。两个串从各自的 0 位置开始一路都对得上一直对到 S1 的 13 位置和 S2 的 13 位置这里对不上了。13 位置的 next 值是 6于是 S2 的比对位置退到 6S1 的 13 位置不动让这两个位置接着比。S1中验证的起点变成 S1 的比对位置减去 S2 的比对位置即 13 减 6 得 7。这一退的含义就是 S2 不再从 S1 的 1 位置开始比对改为从 S1 的 7 位置开始比对。接下来要验的是从S1的 7 位置起把 S2 配出来。S1 的 13 位置对 S2 的 6 位置还是对不上6 位置的 next 值是 3S2 退到 3 位置S1中验证的起点变成 10 位置。S1 的 13 位置对 S2 的 3 位置依然对不上3 位置的 next 值是 0S2 退到 0 位置S1中验证的起点变成 13 位置。S1 的 13 位置对 S2 的 0 位置还是对不上0 位置的 next 值是 -1。这个 -1 说的是 S2 已经退无可退没有位置可退了。代码见到这个 -1不把 S2 的比对位置真改成 -1而是让 S1 换下一个位置从 14 位置重新对上 S2 的 0 位置。把整场匹配的几步列出来走到哪一步S1 的比对位置S2 的比对位置S1中验证的起点还没开始000一路配到对不上13130第一次退1367第二次退13310第三次退13013退不动换起点14014整个过程可以收成一句相等就一起往前不相等就把 S2 的比对位置回退到 next 数组元素的值对应的位置S2 退无可退时S1 的比对位置换下一个位置S2 留在 0 位置。S1 的 1 到 6 和 7 到 12 都不用再和 S2 比一遍S1 从 7 位置开始验证的时候S1 的 7 到 12 这 6 个字符没有重新对一遍直接拿 S1 的 13 位置去对 S2 的 6 位置。敢省掉这一步凭的是 next 值自己的定义。S2 的 13 位置的 next 值是 6意思是 S2 里 0 到 5 这一段和 7 到 12 这一段字符完全一样而且找不到比 6 更长的、相等的前缀和后缀。再补一条已知事实刚才是一路从 0 配到 13 位置才对不上的所以 S1 的 7 到 12 这一段和 S2 的 7 到 12 这一段字符也一样。S2 里 0 到 5 这一段和 S1 的 7 到 12 这一段都等于 S2 的 7 到 12所以它们彼此也相等。也就是说S1 的位置 7 到 12 和 S2 的位置 0 到 5 的字符完全一致。S2 对齐到 S1 的 7 位置之后S1 的 1 到 6 这几个起点也可以直接跳过。因为这几个起点配不出整个 S2。只要反过来推一遍就清楚了。假设里面真有一个起点从它开始能把整个 S2 完整对上。既然能对上S1 从这个起点到 12 位置的一段就得和 S2 的开头一段完全相等。起点还必须在 1 到 6 之间那这一段最少有 7 个字符。S1 的 0 到 12 又是一路配到 13 位置才对不上的所以从起点到 12 位置的同一段也等于 S2 里同样位置的一段。两个说法指的是 S1 里同一段字符于是 S2 的开头一段和 S2 靠后的同样长的一段字符完全一样。开头那段从 0 位置开始是前缀靠后那段一直延伸到 12 位置是后缀。这一对相等的前缀和后缀长度就是起点到 12 位置那段的长度最少 7 个字符比 6 长。可 next 值 6 指的就是最长只到 6。这个数是拿 S2 自己的字符算出来的不会出错。出错的就是刚才那个假设1 到 6 这几个起点都配不出整个 S2直接跳过去没有问题。next 值的二义性6 是 0 到 5 这六个字符的长度而 0 到 5 后面紧跟着的那个字符位置正好也是 6。所以S2退到 6退的是长度也是那段前缀后面那个字符所在的位置。两个说法指着同一格写代码的时候直接用这个数当下标就行。主流程就三个分支不相等的时候S2 的比对位置往回退不会漏掉任何还能配上整个 S2 的机会S1 上跳过的那几个起点本来就不可能配上。这两件事合起来整个匹配过程只剩三种情况。1.两个位置的字符相等两个比对位置一起往后走。2.不相等但 S2 还能退S2 的比对位置退到 next 值上S1 不动。3.不相等S2 退到 0 位置还是对不上S1 换下一个位置重新开始S2 还在 0 位置。intx0;// S1 上正在比对的位置inty0;// S2 上正在比对的位置while(xnym){if(s1.charAt(x)s2.charAt(y)){x;// 相等两个位置一起往后y;}elseif(next[y]-1){// S2 退无可退S1 换下一个起点x;}else{ynext[y];// S1 不动S2 退到 next 值上}}returnym?x-m:-1;// S2 走完说明配上了起点是 x - m代码大白话x和y挨着两边的字符对上了一起往后挪一个位置next[y] -1时单独xS2 已经退到 0 位置还是对不上换 S1 的下一个起点y next[y]S1 不动S2 退到它自己记着的那个位置y mS2 整个配完了说明找到了x - m比对位置往前推 m 个位置就是这段匹配的起点循环走完而y没到 mS1 走到底还没配上返回 -1跳出循环的判据落在 y 上。如果它走到 m说明 S2 从头到尾都配上了这时候 S1 的比对位置往后推 m 个位置就是答案。如果它是被 x 走到底打断的说明 S1 里没有 S2。收尾S1 的比对位置从头到尾只往前没有往回退过这就是 next 数组在匹配里做的事。next 数组自己怎么算出来以及这一路的来回为什么总共只花 O(n m)这两件事放在下一篇。
