LPS(最长前缀，也是后缀)数组的算法复杂度是O(n)？
LPS(最长前缀，也是后缀)数组的算法复杂度是O(n)？
提问于 2021-06-01 18:47:56
下面是我实现的算法，以找到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循环。在最坏的情况下，内部时间将运行j次迭代。这难道不应该使我们的复杂性大于O(n)吗？
我认为证明O(n)复杂性的一种方法是，在内部while循环中，我们没有重复我们的整个逻辑。我们只是将j的值降到0或与ith索引的值相匹配。因此，这一循环被认为是从外部循环的单一迭代的一部分，最终我们的算法的复杂性变成O(n)。
有人能证实这一点或对此提供更多的澄清吗？
回答 1
Stack Overflow用户
回答已采纳
发布于 2021-06-01 19:33:43
j是什么？这是当前前缀的长度。
在每一步，我们使后缀的长度由一个，我们可能会得到更长的同时前缀一个。但是前缀长度可能变小，有时甚至为零。但是如果我们将前缀设置为零长度，并将其逐个扩展，我们就必须执行大量的操作。相反，该算法使用智能优化-前缀长度减少了一个，以重用已计算的信息。
最重要的时刻--前缀减少的总数不能超过字符串长度--这就是复杂性是线性的原因。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/67794477
复制相关文章
相似问题
腾讯云开发者
