查找 LPS（最长前缀也是后缀）数组的算法复杂度如何为 O(n)？

Question

以下是我查找 LPS 数组的算法的实现，它是 KMP 算法的一部分。

public static int[] getLps(String needle)
{
    int[] lps = new int[needle.length()];
    int j = 0;
    lps[j] = 0;

    for (int i=1; i < needle.length(); i++)
    {
        if (needle.charAt(j) == needle.charAt(i))
        {
            j++;
            lps[i] = j;
        }
        else
        {
            while (j != 0)
            {
                j = lps[j-1];

                if (needle.charAt(j) == needle.charAt(i))
                {
                    j++;
                    lps[i] = j;
                    break;
                }
            }
        }
    }

    return lps;
}

在我关注的解释KMP算法的文章中，提到了找出LPS数组的逻辑复杂度是O(n)，这让我有点困惑。在上面的代码中可以看到，for 循环内部有一个内部 while 循环。在最坏的情况下，内部 while 将运行进行 j 次迭代。这不应该导致我们的复杂度大于 O(n) 吗？

我认为证明 O(n) 复杂性合理的一种方法是，在内部 while 循环中，我们没有重复整个逻辑。我们只是减少 j 的值，直到它达到 0 或与第 i 个索引处的值匹配。所以这个 while 循环被认为是来自外部 for 循环的单次迭代的一部分，最终我们算法的复杂度变为 O(n)。

谁能证实这一点或对此提供更多说明？

Answer 1

什么是j？这是当前前缀的长度。

在每一步中，我们都会使后缀长一，我们可能会得到重合的前缀长一。但是前缀长度可能会变小，有时甚至为零。但是如果我们制作零长度的前缀，并且将它一个字符一个字符地扩展，我们必须执行很多操作。相反，此算法使用智能优化 - 前缀长度减一以重用已计算的信息。

最重要的时刻 - 前缀减少的总数不能超过字符串长度 - 这就是为什么复杂度是线性的。

查找 LPS（最长前缀也是后缀）数组的算法复杂度如何为 O(n)？

How is the complexity of algorithm to find LPS(Longest prefix which is also a suffix) array is O(n)?

arrays

algorithm

pattern-matching