《数据结构与算法》——KMP算法

luciferzf

KMP算法：
将关注点从被匹配串转移到模式匹配串上，算法核心就是找到模式匹配串中重复的部分，从而在当某个字符不匹配是找到更高效的移动方式，避免回溯到最开始的状态一点一点地移动。
我们可以建立一个数组存储模式匹配串对应元素若不匹配是徐移动的下标，通常是移动到上一个重复节点，eg.absabc,当c不匹配时，移动到s处数组在c对应位置存储的下标应该为2。