一.KMP算法概念
来看上图，当比较串与模板串比较到AB处不相同时，原始做法是模板串前进一个单位，比较串回溯到开始重新比较，这样做效率低下，很多重复部分。我们要明确一点：模板串与比较串此时的1-2和3-4部分是相同的！所以如果此时串中开头与结尾的一部分是对称相同的，我们可以直接把比较串移动到C处与A比较（而模板串不回溯），这样就能提高效率！来看上图，当比较串与模板串比较到AB处不相同时，
阅读背景：
KMP算法入门
来源：互联网
分享到：
