void getNext(char* p, int* next)
时间: 2023-11-22 07:04:38 浏览: 136
数据结构课设:串的查找,给一文替代换某一个词
这个函数是一个实现 KMP 字符串匹配算法中“求解 next 数组”的函数。其中,参数 p 是要匹配的模式串,next 数组记录了模式串每一位匹配失败时跳转的位置。
具体来说,算法从模式串的第一位开始,维护两个指针 i 和 j,表示当前匹配的位置和已知的部分匹配位置。如果当前位置和已知位置匹配,则两个指针同时向右移动一位,并将 next[i+1] 赋值为 j+1。如果不匹配,则将已知位置 j 向左跳转到 next[j] 所记录的位置,再次进行匹配。
最终,当 i 超过模式串的长度时,next 数组就求解完成了。
阅读全文