KMP算法next'
时间: 2023-11-25 09:37:52 浏览: 30
KMP算法中的next数组是用于记录模式串中每个字符匹配失败后需要回退的位置。next'数组则是next数组的优化版本,用于进一步减少匹配次数。next'数组的求解过程与next数组类似,只是在回退的过程中,将模式串中相同的前缀和后缀进行了一些优化。
具体求解next'数组的步骤如下:
1. 初始化next' = -1、next' = 0。
2. 设置两个指针i和j,分别指向模式串的第1个字符和第2个字符,即i = 1、j = 2。
3. 进入循环,判断两种情况:
a. 如果sub[i-1] = sub[j-1],则next'[j] = next'[i] + 1,然后i++、j++,继续下一轮循环。
b. 如果sub[i-1] != sub[j-1],则将i回退到next'[i]指示的位置,并继续判断。
4. 重复步骤3,直到j = lenSub,其中lenSub是模式串的长度。
最后,得到的next'数组即为KMP算法中的优化next数组。通过使用next'数组进行匹配时,可以进一步减少模式串与主串的匹配次数,提高匹配效率。
相关问题
kmp算法next手算
KMP算法的next数组可以通过手工计算得出。首先,我们需要根据模式串来确定next数组的长度,假设模式串的长度为lenSub。然后,我们可以根据以下规则进行计算:
1. 将next设为-1,next设为0。
2. 初始化两个指针,j表示当前下标,k表示前一项的k,即前一项回退的下标。初始时,j=2,k=0。
3. 在循环中,判断两种情况:
- 情况一:如果k为-1或者sub[j-1与sub[k相等,说明可以继续匹配,此时next[j的值为k+1。然后将j和k分别+1,继续下一个位置的计算。
- 情况二:如果sub[j-1与sub[k不相等,说明当前位置的字符不匹配,需要回退。将k更新为next[k,即回退到前一项的位置。
4. 重复步骤3,直到j达到lenSub为止。
举个例子,假设模式串为"abaabaca",那么可以得到next数组为。
以上是KMP算法next数组的手工计算方法。希望对你有所帮助。<em>1</em><em>2</em><em>3</em>
#### 引用[.reference_title]
- *1* [KMP算法中next数组的手工计算方法](https://blog.csdn.net/wen_alan/article/details/47304723)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT3_1"}} ] [.reference_item]
- *2* *3* [KMP算法——(手把手算next数组)](https://blog.csdn.net/y1355966/article/details/126012669)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT3_1"}} ] [.reference_item]
[ .reference_list ]
KMP算法next数组
KMP算法中的next数组是用来记录模式串中每个位置之前的最长相同前缀后缀的长度。具体来说,next数组的每个元素next\[i\]表示当模式串的第i+1个字符与文本串不匹配时,模式串应该跳过的位置。\[2\]在KMP算法的实现中,通过使用next数组,可以在匹配过程中避免不必要的回溯,提高匹配效率。
next数组的求法有多种方法,其中一种常用的方法是通过动态规划的思想来计算。具体步骤如下:
1. 初始化next数组,将next\[0\]置为-1,next\[1\]置为0。
2. 从模式串的第2个字符开始,依次计算每个位置的next值。
3. 对于位置i,如果模式串的第i个字符与前缀的下一个字符相等,则next\[i\]等于前缀的长度加1。
4. 如果模式串的第i个字符与前缀的下一个字符不相等,则需要根据已知的next值来更新next\[i\]。
- 如果next\[j\]等于-1,或者模式串的第i个字符与前缀的下一个字符相等,则next\[i\]等于j。
- 如果next\[j\]不等于-1,且模式串的第i个字符与前缀的下一个字符不相等,则需要继续向前回溯,即将j更新为next\[j\],然后再进行比较。
- 重复上述步骤,直到找到一个满足条件的j或者回溯到模式串的起始位置。
通过以上步骤,可以得到完整的next数组,用于KMP算法的匹配过程中的跳转操作。\[2\]在KMP算法的代码实现中,可以根据next数组的值来决定模式串的后移位置,从而提高匹配效率。\[3\]
#### 引用[.reference_title]
- *1* *2* [KMP算法&next数组详解](https://blog.csdn.net/ooblack/article/details/109329361)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^control_2,239^v3^insert_chatgpt"}} ] [.reference_item]
- *3* [KMP 算法中的 next 数组](https://blog.csdn.net/m0_52423355/article/details/123807325)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^control_2,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]