KMP算法中求解LPS数组的时间复杂度为何是O(n)？

你的理解完全正确，LPS数组的构建时间复杂度确实为O(n)，嵌套循环不会导致复杂度上升到O(n²)，可以通过摊还分析明确证明这一点：

• 观察核心变量j的变化：j的取值始终在[0, n)区间内（n为模式串长度），仅会在两个场景变化：
  • 外层for循环的匹配分支：当两个位置字符匹配时j加1，外层for循环最多迭代n次，因此j的总增加次数最多为n次
  • 内层while循环分支：每次执行while循环迭代都会执行j = lps[j-1]，根据LPS数组的定义lps[k] ≤ k，因此每次while循环执行都会让j至少减小1
• 由于j不可能为负数，j的总减少次数不可能超过总增加次数，也就是说内层while循环的总执行次数最多为n次
• 整个算法的总操作次数为外层循环的n次加上内层循环最多n次，总操作量级不超过2n，因此时间复杂度为O(n)

小提示：你提供的Java代码可以正常运行，是因为Java的int数组初始化默认值为0，当j=0且字符不匹配时，lps[i]会保持默认的0值刚好符合逻辑。如果使用不会自动初始化数组的编程语言，需要在while循环结束、j仍为0且字符不匹配时，显式为lps[i]赋值0，避免出现未定义行为。

内容的提问来源于stack exchange，提问作者Amar Pawar