计算 “next” 和 “nextval” 是在串中进行模式匹配时经常使用的概念,通常用于字符串匹配算法中的 KMP(Knuth-Morris-Pratt)算法。
在 KMP 算法中,我们需要预先计算出一个称为 “next” 数组的辅助数组,它记录了模式串中每个位置的最长公共前后缀的长度。而 “nextval” 数组是在 “next” 的基础上进行了优化。
具体来说,给定一个长度为 m 的模式串,我们可以通过遍历模式串的每个位置来计算 “next” 数组。下面是计算 “next” 数组的步骤:
-
初始化一个长度为 m 的数组 next,next[0] = -1,表示第一个字符没有最长公共前后缀。
-
遍历 i 从 1 到 m-1,对于每个位置 i:
- 令 j = next[i-1],表示 i-1 位置的最长公共前后缀的长度。
- 不断向前回溯,直到 j >= 0 或者模式串的第 j+1 个字符与模式串的第 i 个字符相等为止。记为条件 j >= 0 && pattern[j+1] != pattern[i]。
- 如果满足上述条件,则令 j = next[j],继续回溯,直到找到一个 j 使得 pattern[j+1] == pattern[i],或者回溯结束(j < 0)。
- 更新 next[i] = j+1。
通过以上步骤,我们可以计算得到 “next” 数组。而 “nextval” 数组则是在 “next” 数组的基础上进行了优化,减少了回溯操作的次数。
在计算 “nextval” 数组时,我们需要进一步优化回溯的过程。具体步骤如下:
-
初始化一个长度为 m 的数组 nextval,其中 nextval[0] = -1,表示第一个字符没有最长公共前后缀。
-
遍历 i 从 1 到 m-1,对于每个位置 i:
- 令 j = nextval[i-1],表示 i-1 位置的最长公共前后缀的长度。
- 不断向前回溯,直到 j >= 0 或者模式串的第 j+1 个字符与模式串的第 i 个字符相等为止。
- 如果满足上述条件,则记为条件 j >= 0 && pattern[j+1] != pattern[i]。
- 如果满足条件 j >= 0 && pattern[j+1] != pattern[i],则令 j = next[j],继续回溯,直到找到一个 j 使得 pattern[j+1] == pattern[i],或者回溯结束(j < 0)。
- 如果满足条件 j < 0 或者 pattern[j+1] != pattern[i],则令 j = -1(即回溯到模式串的开头)。
- 更新 nextval[i] = j+1。
通过以上步骤,我们可以计算得到 “nextval” 数组。这样在 KMP 算法的匹配过程中,可以直接根据 “nextval” 数组进行位置的调整,从而避免不必要的回溯操作,提高算法的效率。
请注意,这里的计算 “next” 和 “nextval” 数组的方法是 KMP 算法的一种实现方式,其他实现方式可能会有所不同,但是核心思想是相似的。
这段代码实现了字符串的模式匹配算法,并计算了KMP算法中的next函数和next函数的修正值。
主要解释一下代码的实现:
-
首先,定义了两个函数:
- get_next2函数用于计算模式串p的next函数。
- get_nextval函数在已有next的基础上求next函数的修正值。
-
在主函数中,定义了模式串p,并输出模式串中的字符。
-
接着,调用get_next2函数计算模式串p的next数组,并输出结果。get_next2函数的实现如下:
void get_next2(string s,vector&next) { next[1]=0; next[2]=1; int k,j; j=2; while(1) { if(j>=next.size()-1)//到达倒数第二个字符,退出循环 break; k=next[j]; while(k!=0) { if(s[j]==s[k]) break; else { k=next[k];//回溯 } } next[j+1]=k+1; j++; } }
- 然后,调用get_nextval函数计算模式串p的next修正值,并输出结果。get_nextval函数的实现如下:
void get_nextval(string p,vectornext,vector &nextval) { nextval=next;//赋值 int j,k; for(j=2;j 在主函数中,使用这两个函数来计算next和next修正值,并输出结果。
完整代码:
#include#include #include using namespace std; //求next函数 void get_next2(string p,vector &next); //求next函数的修正值 void get_nextval(string p,vector next,vector &nextval) ; int main(void) { //string p="$ababaaababaa"; //string p="$aaaabaaaab"; string p="$aaaaaab"; cout<<"模式串为:" < next; next.resize(p.size()); get_next2(p,next); //下面输出对应next函数值 for(int i=1;i<=next.size()-1;i++) cout< nextval; get_nextval(p,next,nextval); for(int i=1;i<=nextval.size()-1;i++) cout< &next) { next[1]=0; next[2]=1; int k,j; j=2; while(1) { if(j>=next.size()-1)//到达倒数第二个字符,退出循环 break; k=next[j]; while(k!=0) { if(s[j]==s[k]) break; else { k=next[k];//回溯 } } next[j+1]=k+1; j++; } } void get_nextval(string p,vector next,vector &nextval) {//在已有next的基础上,取修正值; //不像课本上那样混为一谈。 nextval=next;//赋值 int j,k; for(j=2;j