这个算法是线性的吗？

Question

灵感来自这两个问题:字符串操作:计算"字符串与其后缀的相似性",程序执行随着I/P大小在C中增加超过5而变化,我提出了以下算法.

问题将是

1. 这是正确的,还是我在推理中犯了错误？
2. 算法的最坏情况复杂度是多少？

首先是一些背景.对于两个字符串,将它们的相似性定义为两者的最长公共前缀的长度.字符串s的总自相似性是s与其所有后缀的相似性的总和.因此,例如,总的自相似abacab是6 + 0 + 1 + 0 + 2 + 0 = 9和的总自相似性一重复n次数为n*(n+1)/2.

算法描述:该算法基于Knuth-Morris-Pratt字符串搜索算法,因为字符串前缀的边界起着核心作用.

要概括:一个边界字符串的小号是一个适当的子b的小号它同时是一种前缀和后缀小号.

备注:如果b和c ^是边界小号与b短于Ç,那么b也是一个边界Ç,相反,每一个边界Ç也是一个边境小号.

让小号是长度的串Ñ和p是的前缀小号带长度我.我们所说的边界b与宽度ķ的p 不可伸长如果任一i == n或s[i] != s[k],否则它是可扩展(长度k+1的前缀小号是则长度的边界i+1的前缀小号).

现在,如果最长公共前缀小号,并开始与后缀s[i], i > 0,长度为ķ,长度ķ的前缀小号是长度的不可扩展的边界I + K字头的小号.这是一个边界,因为它是一个共同的前缀小号和s[i .. n-1],如果它是可扩展的,它不会是最长的公共前缀.

相反,(长的每一个不可伸长边界ķ长度)我前缀的小号是最长公共前缀小号和后缀开始s[i-k].

因此,我们可以计算出总的自相似小号由长度的所有非扩展边界的长度相加我的前缀小号,1 <= i <= n.要做到这一点

1. 通过标准KMP预处理步骤计算前缀最宽边框的宽度.
2. 计算前缀的最宽不可扩展边框的宽度.
3. 对于每一个我,1 <= i <= n如果p = s[0 .. i-1]有一个非空非扩展的边界,让b是最宽的这些,加的宽度b和所有非空边界Ç的b,如果它是一个不可扩展的边界p,加上它的长度.
4. 添加长度Ñ的小号中,由于未覆盖的上方.

代码(C):

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

/*
 * Overflow and NULL checks omitted to not clutter the algorithm.
 */

int similarity(char *text){
    int *borders, *ne_borders, len = strlen(text), i, j, sim;
    borders = malloc((len+1)*sizeof(*borders));
    ne_borders = malloc((len+1)*sizeof(*ne_borders));
    i = 0;
    j = -1;
    borders[i] = j;
    ne_borders[i] = j;
    /*
     * Find the length of the widest borders of prefixes of text,
     * standard KMP way, O(len).
     */
    while(i < len){
        while(j >= 0 && text[i] != text[j]){
            j = borders[j];
        }
        ++i, ++j;
        borders[i] = j;
    }
    /*
     * For each prefix, find the length of its widest non-extensible
     * border, this part is also O(len).
     */
    for(i = 1; i <= len; ++i){
        j = borders[i];
        /*
         * If the widest border of the i-prefix has width j and is
         * extensible (text[i] == text[j]), the widest non-extensible
         * border of the i-prefix is the widest non-extensible border
         * of the j-prefix.
         */
        if (text[i] == text[j]){
            j = ne_borders[j];
        }
        ne_borders[i] = j;
    }
    /* The longest common prefix of text and text is text. */
    sim = len;
    for(i = len; i > 0; --i){
        /*
         * If a longest common prefix of text and one of its suffixes
         * ends right before text[i], it is a non-extensible border of
         * the i-prefix of text, and conversely, every non-extensible
         * border of the i-prefix is a longest common prefix of text
         * and one of its suffixes.
         *
         * So, if the i-prefix has any non-extensible border, we must
         * sum the lengths of all these. Starting from the widest
         * non-extensible border, we must check all of its non-empty
         * borders for extendibility.
         *
         * Can this introduce nonlinearity? How many extensible borders
         * shorter than the widest non-extensible border can a prefix have?
         */
        if ((j = ne_borders[i]) > 0){
            sim += j;
            while(j > 0){
                j = borders[j];
                if (text[i] != text[j]){
                    sim += j;
                }
            }
        }
    }
    free(borders);
    free(ne_borders);
    return sim;
}


/* The naive algorithm for comparison */
int common_prefix(char *text, char *suffix){
    int c = 0;
    while(*suffix && *suffix++ == *text++) ++c;
    return c;
}

int naive_similarity(char *text){
    int len = (int)strlen(text);
    int i, sim = 0;
    for(i = 0; i < len; ++i){
        sim += common_prefix(text,text+i);
    }
    return sim;
}

int main(int argc, char *argv[]){
    int i;
    for(i = 1; i < argc; ++i){
        printf("%d\n",similarity(argv[i]));
    }
    for(i = 1; i < argc; ++i){
        printf("%d\n",naive_similarity(argv[i]));
    }
    return EXIT_SUCCESS;
}

那么,这是正确的吗？如果没有,我会感到很惊讶,但我以前错了.

算法的最坏情况复杂度是多少？

我认为它是O(n),但是我还没有找到证据证明前缀在其最宽的不可扩展边界中可以包含的可扩展边界的数量是有界的(或者更确切地说,这种出现的总数是O (N)).

我最感兴趣的是锐界,但是如果你能证明它是例如O(n*log n)或O(n ^(1 + x))x,那就已经很好了.(这显然是最坏的二次方,所以如果伴随着二次或近二次行为的例子,那么"它是O(n ^ 2)"的答案才有意思.)

Answer 1

这看起来像一个非常简洁的想法,但遗憾的是我认为最坏的情况是O(n ^ 2).

以下是我对一个反例的尝试.(我不是数学家所以请原谅我使用Python代替方程来表达我的想法!)

考虑带有4K + 1符号的字符串

s = 'a'*K+'X'+'a'*3*K

这将有

borders[1:] = range(K)*2+[K]*(2*K+1)

ne_borders[1:] = [-1]*(K-1)+[K-1]+[-1]*K+[K]*(2*K+1)

注意:

1)对于i的(2K + 1)值,ne_borders [i]将等于K.

2)对于0 <= j <= K,border [j] = j-1

3)算法中的最后一个循环将进入内部循环,j == K表示i的2K + 1值

4)内循环将迭代K次以将j减少到0

5)这导致算法需要多于N*N/8个操作来执行长度为N的最坏情况的字符串.

例如,对于K = 4,它绕内环循环39次

s = 'aaaaXaaaaaaaaaaaa'
borders[1:] = [0, 1, 2, 3, 0, 1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4]
ne_borders[1:] = [-1, -1, -1, 3, -1, -1, -1, -1, 4, 4, 4, 4, 4, 4, 4, 4, 4]

对于K = 2,248,它绕内环10,111,503次!

也许有一种方法可以解决这种情况的算法？

Answer 2

你可能想看看Z算法,它可证明是线性的:

s是长度为N的C字符串

Z[0] = N;
int a = 0, b = 0;
for (int i = 1; i < N; ++i)
{
  int k = i < b ? min(b - i, Z[i - a]) : 0;
  while (i + k < N && s[i + k] == s[k]) ++k;
    Z[i] = k;
  if (i + k > b) { a = i; b = i + k; }
}

现在相似性只是Z条目的总和.