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

Question

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

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

Answer 1

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