受到以下两个问题的启发：字符串操作：计算“带有后缀的字符串的相似性”，并且随着C中I /
P大小增加到5以上，程序执行也会发生变化，我想到了以下算法。

问题将是

1. 是正确的，还是我的推理有误？
2. 该算法的最坏情况复杂度是多少？

先说一下上下文。对于两个字符串，将它们的相似性定义为两者中最长的公共前缀的长度。字符串 s 的总自相似度是 s
与所有后缀的相似度之和。因此，例如，总的自相似 abacab 是6 + 0 + 1 + 0 + 2 + 0 = 9和的总自相似性 一
重复n次数为n*(n+1)/2。

算法说明： 该算法基于Knuth-Morris-Pratt字符串搜索算法，其中字符串前缀的 边界 起着核心作用。

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

备注：如果 b 和 c 是 s的 边界，且 b 短于 c ，则 b 也是 c 的边界，反之， c的 每个边界也是 s
的边界。

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

现在，如果最长公共前缀 小号 和后缀开始s[i], i > 0，长度为 ķ ，长度 ķ 的前缀 小号 是长度的不可扩展的边界 I +
K 的前缀 小号 。这是一个边界，因为它是 s 和的公共前缀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））。

我对尖锐边界最感兴趣，但是如果您可以证明它对于小x，例如O（n * log n）或O（n ^（1 +
x）），那已经很好。（显然，这是最糟糕的二次方，因此，只有伴随二次方或接近二次方行为的示例时，“ It’s O（n ^ 2）”的答案才有意义。）