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 ]