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

Question

Вдохновленный этими двумя вопросами: String manipulation: calculate the "similarity of a string with its suffixes" и Program execution varies as the I/P size increases beyond 5 in C, я придумал приведенный ниже алгоритм.

Вопросы будут

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

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

Описание алгоритма: Алгоритм основан на струне Кнут-Морриса-Пратта алгоритм поиска, в том, что границы префиксов струны играют центральную роль.

Повторим: в границе строки с является собственными подстроками б из с, который одновременно является префикс и суффикс с.

Примечание: Если б и с являются границами с с б короче с, то б также граница с, и наоборот, каждая граница c также является границей s.

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

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

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

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

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

код (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) ne_borders [i] будет равно K для (2K + 1) значений i.

2) при 0 = < < J = К, границы [J] = J-1

3) заключительный цикл в вашем алгоритме будет идти во внутреннюю петлю с J == K для 2k + 1 значения I

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 является C-строка длиной N

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.