KMP算法的理解与实现 这里不做完整的讲解,只说核心部分. KMP与朴素字符串匹配最大不同在于:KMP试图利用已经比较了的信息. 如果KMP已经部分匹配了模式字符串p[0,i),发现p[i]无法匹配上目标字符串,就试图寻找可以利用的部分匹配结果. 试想,如果p[0,j)和p[i-j+1,i)相同,并且j在[0,i-1]范围内,那么可以直接从p[j]开始新一轮匹配.也就是说,只要找到p[0,i)中部分前缀和部分后缀相同的情况. 这份实现是在做lintcode时的提交代码.