那些是flash做的网站,seo关键词推广渠道,郑州怎样建设公司网站,外贸做网站公司求KMP的算法### 求next数组方法#xff1a;
首先求每个子串的最长前后缀
1、next 数组的定义 next 数组#xff08;前缀表#xff09;是在 KMP 算法中使用到的#xff0c;用于匹配模式串相同前后缀长度
它可以减少匹配次数#xff0c;其原理是将模式串中每个子串的相同…求KMP的算法### 求next数组方法
首先求每个子串的最长前后缀
1、next 数组的定义 next 数组前缀表是在 KMP 算法中使用到的用于匹配模式串相同前后缀长度
它可以减少匹配次数其原理是将模式串中每个子串的相同前后缀长度记录下来当在文本串中匹配失败时就根据前缀表——即 next 数组——找到模式串中匹配失败前一个字符的位置所对应的前缀尾字符将模式串的指针移动到该字符
过程说明 下标从0开始 0 1 2 3 4 5 6 7 8 文本串 a a b a a b a a f 模式串 a a b a a f next 数组 0 1 0 1 2 0 右移补-1的next 数组 − 1 0 1 0 1 2 模式串 a a b a a f 下标从1开始 1 2 3 4 5 6 7 8 9 右移补-1的基础上整体加1的next 数组 0 1 2 1 2 3 \begin{array}{|r|l|l|l|l|l|l|l|l|l|l|} \hline \text { 下标从0开始 } \mathbf{0} \mathbf{1} \mathbf{2} \mathbf{3} \mathbf{4} \mathbf{5} \mathbf{6} \mathbf{7} \mathbf{8} \\ \hline \text { 文本串 } \mathrm{a} \mathrm{a} \mathrm{b} \mathrm{a} \mathrm{a} \mathrm{b} \mathrm{a} \mathrm{a} \mathrm{f} \\ \hline \text { 模式串 } \mathrm{a} \mathrm{a} \mathrm{b} \mathrm{a} \mathrm{a} \mathrm{f} \\ \hline \text { next 数组 } 0 1 0 1 2 0 \\ \hline \text { 右移补-1的next 数组 } -1 0 1 0 1 2 \\ \hline \text { 模式串 } \mathrm{a} \mathrm{a} \mathrm{b} \mathrm{a} \mathrm{a} \mathrm{f} \\ \hline \text { 下标从1开始 } \mathbf{1} \mathbf{2} \mathbf{3} \mathbf{4} \mathbf{5} \mathbf{6} \mathbf{7} \mathbf{8} \mathbf{9} \\ \hline \text { 右移补-1的基础上整体加1的next 数组 } 0 1 2 1 2 3 \\ \hline \end{array} 下标从0开始 文本串 模式串 next 数组 右移补-1的next 数组 模式串 下标从1开始 右移补-1的基础上整体加1的next 数组 0aa0−1101aa10212bb01a323aa10a414aa21b525bf02a636aa77af88f9 求next数组方法
求每个字串对最长前后缀 a的最长前后缀为0aa的最长前后缀为1aab的最长前后缀为0aaba的最长前后缀为1aabaa的最长前后缀为2aabaaf的最长前后缀为0求得最长前后缀数组为[0,1,0,1,2,0] 右移补-1得到next数组目的就是让失配点的下标直接指向字符长为5的最长前后缀的下一个位置开始匹配最长前后缀的位置一定会失配因此跳过。如果数组下标从1开始就整体加1。【总结】第一位-1求1到n位子串前后缀长度得到数组将得到的数组整体加1。
