数据结构中KMP算法的时间复杂度

KMP算法的时间复杂度为O(m+n)

所以说到底是O(m+n）还是O(n)

预处理短字符串的时间复杂度是O(m)，生成next数组，m为短字符串的长度。
进行比较的时间复杂度是O(n)，n为长字符串的长度。
所以整体时间复杂度是O(m+n)，但进行查找的复杂度只有O(n)，比如在很多不同的长字符串里查找同一个短字符串

• 文章：KMP模板(复杂度O（m+n）)（新） 中也许有你想要的答案，请看下吧
• 除此之外, 这篇博客: 408知识复试前摘要复习中的 KMP O(m+n) 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 其实kmp算法的思想就是，也是相当于使用了两个指针，一个指针i指向了字符串s中的字符，一个指针j指向了字符串p中的字符，朴素的做法是当si 和 pj 匹配失败的时候，i指针回退到主串匹配开始的位置+1那个地方，模式串回退到模式串开始的地方，然后再进行配对。但是，由于之前我们主串和模式串已经匹配了一部分了，我们可以利用这部分的信息来减少配对的次数。
  我们给模式串一个next数组，next[i] 的含义表示从0~i-1 号的字串中，前k个字符恰好等于后k个字符的最大的k的值。然后下次匹配的时候，我们的主串的i指针就不移动，依然指向了上次失败的位置，然后我们的模式串的指针这次不移动到开始了，这次移动到号码为next[j]的那个位置上，从这个位置再进行匹配，这样就极大的减少了i指针的回退次数，提高了效率。
  next[i]表示模式串i号位置匹配失败时，下一次模式串的指针指向哪里。
  求那个next数组可以就是用两个指针一个从i-1向前搜，一个从0向后搜。