java - KMP前缀表运行时间

Question

我写了一个代码来填充 KMP 的前缀表。这是这个 algorithm 的小变化.我无法说服自己这个算法/​​实现在 O(n) 时间内运行。我很难弄清楚第二次递归调用对总运行时间的影响。有帮助吗？

    public void fillFailTable(int[] failTable,String p){
        failTable[failTable.length-1] = preLength(failTable,p);
    }

    private int preLength(int[] failTable,String s){

        if(s.length() == 1){
            return 0;
        }
        int n = s.length();
        int k = preLength(failTable,s.substring(0,n-1));

        failTable[n-2] = k;

        if(s.charAt(k) == s.charAt(n-1)){
            return k+1;
        }else{
            return preLength(failTable,s.substring(n-1-k));
        }
    } 

Answer 1

这实际上很有趣(我仍然想知道为什么没有比我更聪明的人回答这个问题)。请对这个解释持保留态度，因为我不是 100% 确定这是否接近正确(尽管我可以 100% 告诉你这个方法在 O(n) 中运行，因为这是他们在大学几年前，但他们并没有费心去解释它，呃，所以我不得不自己想出它)。

好吧，让我们从 s.length = 2 的一个非常基本的例子开始。事先要提到两件事:

• 在每个示例中，让我们只担心最坏的情况，因为我们对 Big Oh 感兴趣，这意味着我们进入第二个 preLength() 方法。
• 我们可以观察到，在寻找 Big Oh 时，此代码中的“k”(以及 preLength() 返回的值)将始终为 0，您会在下图中注意到这一点，即 真的很重要。

s.length == 2

我们首先进入第一个 preLength() 方法(我们称它为 *)，现在用 s.length = 1 调用它并立即返回 0。现在因为我们只考虑最坏的情况(意思是 s .charAt(k) != s.charAt(n-1)) 我们输入第二个 preLength() 也是一个长度为 1 的字符串(因为 n=2 和 k=0)。这个也立即返回一个 0 给我们的 *。这结束了我们的方法调用。我们总共有 3 个方法调用。我们的 * 和两个 preLength()。这是一张图片:

s.length == 3

现在让我们看一个起始 s.length = 3 的示例。正如您所注意到的，我们立即调用了 s.length = 2 的 preLength() 并且，从我们之前的示例中，我们知道这个需要 3 个方法调用。现在我们需要记住，当方法 preLength(2) 这次返回时，它返回到我们的原生 preLength(3)，它现在将再次调用 preLength(2)(else 中的那个)，这将再次需要 3 次方法调用。所以我们总共需要 2*3+1 次方法调用。这给了我们 7。同样，这里有一个图像(圆圈是 preLength 的调用，字符串的长度如圆圈所示):

结论

现在您可以看到所有这些方法调用都是对称的 - 那是因为我们的 k 始终 等于 0，这意味着第二个 preLengt() 将是使用与第一个相同大小的字符串调用 - 当我们知道 需要多少个时，我们可以看到 s.length = m 需要多少个m-1 因为 f(m) = 2*f(m-1)+1 其中 f(m) 是告诉我们有多少方法的函数我们需要为大小为 m 的字符串计算表的调用。这是有效的，因为正如我之前所说，方法调用是对称的(那是因为在最坏的情况下 k=0 总是并且 preLenght() 总是返回 0，因此 2* 并且我们需要添加 1 个方法调用，我们调用的第一个)。

所以基本上随着我们输入的每次增量(m 的大小)，计算时间增长 2 倍加一 (2*m+1)，据我所知，这意味着这种方法在最坏的情况下是情况，O(n)。

正如我所说，请对这个持保留态度，但我希望这是有道理的 :)