改进的kmp算法next数组的求法
时间: 2025-01-03 17:24:26 浏览: 83
### 改进 KMP 算法 Next 数组计算方法
#### 定义与作用
Next数组记录的是模式串中各个位置的最大相同前缀和后缀长度,这一特性使得在匹配过程中遇到不匹配情况时可以快速调整模式串的位置而不必回溯主串指针。这大大提高了字符串匹配效率[^2]。
#### 计算过程解析
为了更清晰地理解`next`数组的构建逻辑,下面给出具体的计算流程:
- 初始化两个索引变量 `i` 和 `j` ,其中 `i` 表示当前正在处理的字符位置(从1开始),而 `j` 则指向已知最长公共前后缀结束处之后的一个位置(初始设为 `-1` 表示尚未找到任何匹配)。同时设定 `next[0]=-1` 作为边界条件。
- 当遍历至某位时如果发现该位之前存在相同的前后缀,则更新 `next[i]=j+1` 。这里需要注意的是,在某些情况下可能需要多次回退 `j` 的值直到满足上述条件为止;此时应依据先前存储于 `next[]` 中的信息来进行跳跃式的查找操作而不是逐个比较每一个字符。
- 如果两者并不相等且 `j>-1` (意味着还有机会继续寻找其他潜在的可能性),那么就按照 `next[j]` 所指示的方向移动 `j` 并重复以上步骤直至最终确定合适的映射关系或者确认不存在这样的子序列结构。
```cpp
void get_next(const string &pattern, vector<int> &next){
int j = -1;
next.resize(pattern.size());
next[0] = -1;
for(int i = 1; i < pattern.size(); ++i){
while(j >= 0 && pattern[j + 1] != pattern[i])
j = next[j];
if (pattern[j + 1] == pattern[i])
++j;
next[i] = j;
}
}
```
此段代码实现了对给定模式串`pattern`构造对应的`next`数组的功能。通过循环迭代的方式逐步填充每一项的具体数值,并巧妙运用了双指针技巧来简化问题求解难度并提高运行速度。
#### 示例说明
假设有一个模式串 `"ababc"` , 那么根据上面介绍的方法依次计算得到如下所示的结果:
| 字符 | a | b | a | b | c |
| --- |---|---|---|---|---|
| 下标 | 0 | 1 | 2 | 3 | 4 |
| next | -1 | 0 | 0 | 1 | 2 |
解释:对于第四个字符 'b' 来说,它前面有 "aba" 这样的子串,显然这个子串具有长度为1的共同前缀 ("a") 和 后缀 ("a"),因此对应位置上的`next`值被设置成了1(即上一个'a'所在的位置);同理可得第五个字符'c'之前的最长相等前后缀长度为2.
阅读全文
相关推荐


















