一个字符串，匹配模式串的过程。在对齐比较模式串的时候，如果发现第n位不匹配，那么对于n位之前的模式子串进行分析。找出这个子串中最长的头尾相同的串，也就是公共前后缀。然后模式串可以移动到后缀进行比较。如果没有找到，则模式串的头部直接移动到不匹配的字符这里。这样大大加快比较的速度。比较指针永远不需要往回退再比较，只需要继续比较后面的字符。
疑问在于，为什么可以这样移动？不会漏掉中间能够匹配的情况吗？答案是不会。为什么呢？可以逆向思考这个问题，假设在中间还有能够匹配的情况，则必然存在比前面我们找出的最长的公共前后缀更长的前后缀，因为移动到任何位置能匹配的话，就代表尾部必然存在一个相同的后缀。因为之前我们已经找到最长的前后缀，所以这个后缀必然不存在。
理解到此，我们基本可以理解为什么只需要找到最长的公共前后缀，并根据这个进行移动。
因为比较指针可以在任何位置发现不同，也就是说前面的前后缀的分析，需要对于模式串任意长度都进行分析。而同时我们发现任何位置上进行这个最长公共前后缀的分析是和匹配字符串是无关的，只和模式串相关。
所以对于任意位置的发现的不同，需要移动的距离仅仅和模式串自身相关。也就是说，我们可以对于模式串的任意位置的不同，找出一个最长的公共前后缀，而这个后缀就是要移动的位置。这个最长前后缀因为仅仅和模式串相关，对于任意位置的比较的不同，它必然是固定的。也就是说它是模式字符串每一个位置的函数。这个子缀的长度决定了需要模式串移动的距离。假设现在是第n位不同，那么n-1 - 最长公共前后缀长度，就是模式需要移动的距离。
对于下标从1开始的模式串，如果n位不同，公共前后缀长度为m, 则对应于n位的移动下标值为m+1。
证明如下:
如果第n位不同，则前面相同的长度为n-1, 比如如果第一位就不同，则前面相同的长度为n-1 = 0。这也就是为什么需要下标从1开始的原因。方便计算。
如果公共前后缀的长度为m，那么实际上模式字符串需要移动的距离为前面相同的长度-公共前后缀的长度。也就是n - 1 - m
本来n位的模式串的下标为n， 模式字符串往前移动n-1-m的距离后，原来的n的位置的变成了新的下标为 n - (n-1-m) = n -n +1 +m = m + 1
也就是说n位对应的移动下标为m+1，也就是最长公共前后缀的长度+1
证明完毕。
实际匹配中，这样操作。对齐匹配串和模式串，发现第n位不同，根据上面求出的对应该位置的函数值，移动模式串，然后继续往前移动比较指针。如果比较指针移动到模式串的尾部，说明发现了匹配的位置。返回结果。如果移动指针超出了匹配串，说明没有找到比较结果。
对于上面的不同位置求解函数值的过程，就是所谓的计算匹配数组的过程。
网友评论