本文主要是介绍蛮力法之串匹配问题---kmp算法中真/后缀作用及next数组计算，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
在源串S中搜索目标串T时，利用串匹配的暴力求解方法，在求解的过程中，我们分析得到简化该问题求解过程的关键步骤，也即kmp算法的核心思想：如何在某趟S[i]和T[j]匹配失败时，下标i不回溯，下标j回溯到某个位置k，下一趟搜索时，从T[k]和S[i]开始比较。这样可以使得算法复杂度降低到O(n)，其中n为源串S的长度。
一、什么是真前缀和真后缀
真前缀就是对T[j]来说，使得T[0]~T[k-1]=T[j-k]~T[j-1]，k取最大值时的子串T[0]~T[k-1]，同理
真后缀就是对T[j]来说，使得T[0]~T[k-1]=T[j-k]~T[j-1]，k取最大值时的子串T[j-k]~T[j-1]
直观来说就是，就是在子串T[0]~T[j-1]中，k从取值范围[0，(j-1)/2]中逐渐增大，使得
从下标0开始向后增加构建子串T1=T[0]
T1=T[0]T[1]
T1=T[0]T[1]T[2]
......
T1=T[0]T[1]T[2]···T[k-1]
从下标j-1开始向前减小构建子串T2=T[j-1]
T2=T[j-2]T[j-1]
T2=T[j-3]T[j-2]T[j-1]
......
T2=T[j-k]···T[j-3]T[j-2]T[j-1]
在构建子串T1，T2的过程中，依次比较
T1=T[0]是否与T2=T[j-1]相等：若相等，进行下一轮的T1，T2的构建与比较；
T1=T[0]T[1]是否与T2=T[j-2]T[j-1]相等：若相等，再进行下一轮的T1，T2的构建与比较；
依次类推，直到k取得最大值(j-1)/2时结束；
在T1，T2的比较过程中，如果出现T1不等于T2的情况，则T1，T2的构建与比较过程结束，k取使得T1=T2时的最大值，此时对应的
真前缀就是T[0]~T[k-1]
真后缀就是T[j-k]~T[j-1]
二、为什么要计算真前缀和真后缀
在如下的搜索比较时出现S[i]不等于T[j]：
S[0]S[1]··········S[i-3]S[i-2]S[i-1]S[i]··········S[n-3]S[n-2]S[n-1]
T[0]·········T[j-2]T[j-1]T[j]······T[m-1]
显然字符串 T[0]~T[j-2]T[j-1]等于字符串S[i-j]~S[i-2]S[i-1]，它们的长度为j
显然它们的子串T[j-k]~T[j-1]等于S[i-k]~S[i-1]，它们的长度为k
这时，利用T[j]的真前缀和真后缀T[0]~T[k-1]=T[j-k]~T[j-1]，
所以T[0]~T[k-1]等于S[i-k]~S[i-1]
根据KMP算法思想，i不动，j需要回溯到某一个位置，根据上面的分析，j需要回溯到位置k，即下一次比较从S[i]和T[k]开始，也即：
S[0]S[1]··········S[i-3]S[i-2]S[i-1]S[i]··········S[n-3]S[n-2]S[n-1]
T[0]····T[k-1]T[k]···T[j-1]T[j]···T[m-1]
这也体现了真前缀和真后缀得作用。
三、next数组计算
若已找到T[j]的真前缀和真后缀，也即T[0]~T[k-1]=T[j-k]~T[j-1]，在求T[j+1]的真前缀和真后缀时，分两种情况：
（1）T[k]=T[j]，则T[j+1]的真前缀和真后缀为T[0]~T[k-1]T[k]=T[j-k]~T[j-1]T[j]
（2）T[k]不等于T[j]，那么需要在T[0]~T[j]中寻找真前缀和真后缀，分析得到如下结论：
（i）因为T[0]~T[k-1]=T[j-k]~T[j-1]，所以由真前缀和真后缀得定义可以推断出字符串T[0]~T[k-1]关于T[k]和T[j-k]~T[j-1]关于T[j]的真前缀和真后缀是一样的，所以得到结论T[0]~T[k-1]关于T[k]的真前缀等于T[j-k]~T[j-1]关于T[j]的真后缀；
（ii）结论：next[k]的值为T[0]~T[k-1]的真前缀和真后缀的字符串长度，正如next[j]的值为字符串T[0]~T[k-1]的长度；
根据以上（i）和（ii）结论，
令k=next[k]，
若T[k]=T[j]，也即T[next[k]]=T[j]，则next[j+1]=k+1，解释如下：
根据结论（i）可以得到T[0]~T[next[k]-1]=T[j-next[k]]~T[j-1]，又因为T[next[k]]=T[j]，可以得到T[0]~T[next[k]-1]T[next[k]]=T[j-next[k]]~T[j-1]T[j]该式满足T[0]~T[j+1]关于真前缀和真后缀的定义，所以next[j+1]=k+1;
若T[k]不等于T[j]，则继续寻找T[0]~T[next[k]]的真前缀，此时继续令k=next[k]，
直到T[k]=T[j]（此时next[j+1]=k+1），
或者直到k=-1(此时next[j+1]=0)。
根据如上讨论可以计算得到next数组。
这篇关于蛮力法之串匹配问题---kmp算法中真/后缀作用及next数组计算的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
