04-4.2.3 KMP 算法求 next 数组

• 👋 Hi, I’m @Beast Cheng
• 👀 I’m interested in photography, hiking, landscape…
• 🌱 I’m currently learning python, javascript, kotlin…
• 📫 How to reach me --> 458290771@qq.com

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑‍💻
此外，《程序员必备技能》专栏日后会逐步更新，感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏

举例：有一个模式串 google ，分别对应 1~6 ，在 next 数组中也是从 next[1~6]

next 数组的作用：当模式串的第 j 个字符失配时，从模式串的第 next[j] 个继续往后匹配

分析：
对于任何模式串来说都一样

• 第一个字符不匹配时，只能匹配下一个子串，因此，next[1]无脑写 0 即可
• 第二个字符不匹配时，应该尝试匹配模式串的第一个字符，因此，next[2] 无脑写 1
• 对于 next[3] 来说，在不匹配的位置的前面，画一条分界线，模式串一步步往后退，知道分界线前的“能对上”，或者模式串完全跨过分界线为止。此时 j 指向哪里，next 数组的值就是多少
• 对于 next[4], next[5], next[6] 来说和 next[3] 一样