Вдохновлены этими двумя вопросами: Манипуляции со строками: вычислите "сходство строки с ее суффиксами" и Выполнение программы варьируется при увеличении размера ввода-вывода более 5 в C , Я придумал приведенный ниже алгоритм.
Вопросы будут
- Правильно, или я ошибся в своих рассуждениях?
- Что такоев худшем случае сложность алгоритма?
Сначала немного контекста.Для двух строк определите их сходство как длину самого длинного общего префикса из двух.Общее самоподобие строки s является суммой сходств s со всеми ее суффиксами.Так, например, общее самоподобие abacab составляет 6 + 0 + 1 + 0 + 2 + 0 = 9, а полное самоподобие a повторяется n разis n*(n+1)/2.
Описание алгоритма: Алгоритм основан на алгоритме поиска строки Кнута-Морриса-Пратта, в котором граничит строкипрефиксы играют центральную роль.
Подводя итог: border строки s - правильная подстрока b из s , который одновременно является префиксом и суффиксом с .
Примечание: если b и c являются границами с с b короче c , тогда b также является границей c , и наоборот, каждая граница c также является границей s .
Пусть s будет строкой длины n и p будет префиксом с длиной 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 <= i <= n.Для этого
- Рассчитать ширину самых широких границ префиксов с помощью стандартного шага предварительной обработки KMP.
- Рассчитать ширину самых широких нерасширяемых границ префиксов.
- Для каждого i ,
1 <= i <= n, если p = s[0 .. i-1] имеет непустую нерасширяемую границу, пусть b будет самой широкой из них, добавьте ширину b и для всех непустых границ c из b , если это нерастяжимая граница p , добавьте еедлина. - Добавьте длину n из с , поскольку это не указано выше.
Код(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)» интересен, только если сопровождается примером для квадратичного или почти квадратичного поведения.)