注意到 , 对于主串中的某一最长可匹配后缀子串,在当前状态下是已经匹配上的 。如果在模式串中找到了另一个合法的最长可匹配前缀子串,那我们就将其进行滑动 。说明,如果可以滑动,那么在模式串中,一定存在两个不同起始位置的子串 , 且这两个子串的内容是相同的 。因此我们可以用这个信息,在只依赖模式串的情况下完成规律的查找与构建 。
数学化表达:对于模式串 t 的每个元素 t[j],都存在一个实数 k,使得模式串 t 开头的 k 个字符( t[ 0 ], t[ 1 ],…, t[ k-1 ] )依次与 t[ j ] 前面的 k 个字符( t[ j-k ], t[ j-k+1 ],…, t[ j-1 ] ) 相同(其中,字符 t[ j-k ] 最少从 t[ 1 ] 开始,须保证不重复 , 所以 k < j ) 。。如果这样的 k 有多个,则取最大的一个,以此保证最长 。模式串 t 中每个位置 j 的字符都适配这种规律,定义一个 next 数组存储这种规律,即 next[ j ] = MAX{ k } 。
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S21933I-42.png)
文章插图
对于 next 数组,其索引表示当前比较的两个字符的位置 ‘j’ ;索引对应值表示 k。若当前字符为坏字符,则可以滑动 j – k 位,即下一次的比较位置 。
(1) 当模式串的第一个字符和主串不匹配时,并不存在已匹配前缀子串 , 更不存在最长可匹配前缀子串,因此next数组下标是0 , next[ 0 ]的元素值也是0 。
(2) 如果已匹配前缀是 “G”、“GT”、“GTGTGC”,但其并不存在最长可匹配前缀子串,所以对应的next数组元素值(next[ 1 ] , next[ 2 ],next[ 6 ])同样是0 。
(3) 对于好前缀 “GTG”,此时比较位置为索引 j = 3,从该位置向前找最长可匹配前缀子串;从开头找最长可匹配后缀子串,得出最长可匹配前缀是 ‘G’,即 k = 1(此时滑动 j – k = 2 位) 。因此,对应数组中的next[ 3 ],元素值是k = 1(即,下一次的比较位置) 。以此类推,“GTGT” 对应 next[ 4 ] , 元素值是2;“GTGTG“ 对应 next[ 5 ],元素值是3 。
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S21945A-43.png)
文章插图
小结:用一个数组保存每个字符的信息,当在该字符处不匹配时,通过数组保存的信息,退回到相应位置 。其中,数组的下标表示“当前比较两个字符的位置 j”,元素的值则是“最长可匹配前缀子串的下一个位置 《=》 最长可匹配前缀子串的长度 《=》 MAX{ k }” 。
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
- 如何构建next数组?【重难点】
由于已匹配前后缀子串仅在模式串中查找,与主串无关 。所以仅依据模式串,即可生成next数组 。
最简单的方法是从最长的前缀子串开始 , 把每一种可能情况都做一次判断 。假设模式串的长度是m,生成next数组所需的最大总判断次数是1+2+3+4+......+m-2 次 。
显然,这种方法的效率非常低,整体近似 n2 的量级 。因此 , 可以采用类似“动态规划”的方法 。首先next[ 0 ]和next[ 1 ]的值肯定是0,因为不存在前后缀字串;从next[ 2 ]开始,next数组的每一个元素都可以由上一个元素推导而来 。
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S2192S4-44.png)
文章插图
设置两个变量i和j,其中i表示“当前比较两字符的位置”,也就是待填充的数组下标;j表示“最长可匹配前缀子串的下一个位置”,即转跳回来的下一次比较位置,也就是待填充的元素值 。分析可知,此时最长可匹配前缀子串不存在,所以当 i = 0 时 , j = 0,next[ 0 ] = 0 。
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S21910E-45.png)
文章插图
继续向后移动当前比较的位置 。此时存在字符串 “G“ , 由于只有一个字符,不满足 k < j 的条件 。因此,同样不存在最长可匹配前缀子串,所以当 i = 1 时,j = 0,next[ 1 ] = 0 。
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S21a339-46.png)
文章插图
此时的已匹配前缀是 “GT”,由于模式串当中 pat[ j ] != pat [ i-1 ],即’G’ != ‘T’ , 最长可匹配前缀子串仍然不存在 。所以当 i = 2 时,j = 0,next[ 2 ] = 0 。
![.NET源码学习 [算法2-数组与字符串的查找与匹配]](http://img.zhejianglong.com/231017/1S219EO-47.png)
文章插图
继续后移 。此时的可匹配前缀是 “GTG“ , 此时模式串中 pat [ j ] == pat [ i-1 ],即 ‘G‘ = ’G‘,最长可匹配前缀子串出现了,是 ”G“ 。
推荐阅读
- 【前端必会】不知道webpack插件? webpack插件源码分析BannerPlugin
- 20220929-ArrayList扩容机制源码分析
- Optional源码解析与实践
- Go 源码解读|如何用好 errors 库的 errors.Is 与 errors.As() 方法
- .Net下的分布式唯一ID
- .NET 反向代理 YARP 代理 GRPC
- 赞美父亲的作文结尾 赞美父亲的高中作文
- 关于对自己有信心的名言名语 对学习有信心的名言
- 关于父亲的高中作文800字 关于父亲的高中作文
- 高一化学全面学习方法整理