KMP算法的时间复杂度为O(m+n) 。
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。KMP算法的时间复杂度为O(m+n)。
首先想到的一定是质朴做法，从每一个元素开始搜，但是这样坐在不友好的数据下复杂度能达到O(m*n)，这肯定会T起飞的。那么该怎么优化呢？思考在质朴做法中，有哪些是重复进行的？拿一个样例就懂了：模式串：abcabc，文本串：abcabdababcabc。
先质朴思路，从前往后搜索...abcab。下一个c和d没有对上，那么按照质朴算法，是不是要往右一位重新开始匹配？
但是仔细观察一下，在已经搜索过的abcab中，是不是往右移3步即移动到末尾的ab时才能继续匹配？那就记录下来相同的前后缀abc，这样能直接从前一个abc跳到下一个。这就是KMP思路的精髓，在匹配失败后不会一步一步的往后搜，而是利用已经搜过的过程中找到一个公共前后缀开始搜。
KMP的时间复杂度分析：
假设m为模式串strM的长度，n为待匹配的字符串strN的长度。O(m+n)+O([m,2m]+[n,2n])=计算next数组的时间复杂度+遍历比较的复杂度。也就是：计算next数组时的比较次数介于[m,2m]。遍历比较的比较次数介于[n,2n]，最坏情形形如T=“aaaabaaaab”，P=“aaaaa”。所以算法时间复杂度是O(m+n)。
这里分析下[n,2n]的最坏情况是怎么得出的，可以抽象下这样理解，遍历待匹配字符串strN时，比较strN[i]、strM[j]时可能的情况为：
1、当前字符匹配时，同时移动i++，j++。2、当前字符不匹配，且j=0时，只移动i++，j=0不动。3、当前字符不匹配，且j!=0时，i不变，strM[j]回跳，最多跳j次，但j由前面匹配的情况1确定，而情况1总共不可能出现超过n次，所以总回跳不会超过n次。所以最坏情况，i++次数（情况一+情况二）+j回跳（情况3）=n+最坏n=2n。[m,2m]也可以类似证明。