Является ли этот алгоритм линейным?

Вдохновленный этими двумя вопросами: Работа со строкой: вычислить "сходство строки с ее суффиксами" и Выполнение программы меняется при увеличении размера I/P больше 5 в C, я придумал следующий алгоритм.

Вопросы будут следующие

1. Правильный ли он, или я допустил ошибку в своих рассуждениях?
2. Какова наихудшая сложность алгоритма?

Сначала немного контекста. Для двух строк определите их сходство как длину самого длинного общего префикса. Общее самоподобие строки s равно сумме сходств s со всеми ее суффиксами. Так, например, полное самоподобие abacab равно 6 + 0 + 1 + 0 + 2 + 0 = 9, а полное самоподобие a, повторенного n раз, равно n*(n+1)/2.

Описание алгоритма: Алгоритм основан на алгоритме поиска строки Knuth-Morris-Pratt, в котором центральную роль играют границы префиксов строки.

Напомним: граница строки s - это правильная подстрока b из s, которая одновременно является префиксом и суффиксом s.

Замечание: Если b и c - границы s, причем b короче c, то b также является границей c, и наоборот, каждая граница c также является границей s.

Пусть s - строка длины n, а p - префикс s длины i. Мы называем границу b шириной k из p нерасширяемой, если либо i == n, либо s[i] ! = s[k], иначе он расширяемый (длина k+1 префикса s тогда является границей длины i+1 префикса s).

Теперь, если самый длинный общий префикс s и суффикс, начинающийся с s[i], i > 0, имеет длину k, то префикс k длины s является нерастяжимой границей префикса i+k длины s. Это граница, потому что она является общим префиксом s и s[i ... n-1], и если бы она была растяжимой, то не была бы самым длинным общим префиксом.

И наоборот, каждая нерастяжимая граница (длины k) длины i префикса s является самым длинным общим префиксом s и суффикса, начинающегося с s[i-k].

Поэтому мы можем вычислить общее самоподобие s, суммируя длины всех нерастяжимых границ длины i префиксов s, 1 . Для этого

1. Вычислите ширину самых широких границ префиксов стандартным шагом предобработки KMP.
2. Вычислите ширину самых широких нерасширяемых границ префиксов.
3. Для каждого i, 1 , если p = s[0 ... i-1] имеет непустую нерастяжимую границу, пусть b будет самой широкой из них, добавьте ширину b и для всех непустых границ c из b, если это нерастяжимая граница p, добавьте ее длину.
4. Добавьте длину n от s, так как она не охватывается вышеперечисленным.

Код (C):

#include 
#include 
#include 

/*
 * 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)" интересен только в том случае, если он сопровождается примером квадратичного или близкого к квадратичному поведения)