Вдохновленный этими двумя вопросами: Обработка строк: вычислить "сходство строки с суффиксами" и Программа исполнение меняется, поскольку размер I/P увеличивается до 5 в C, я придумал ниже описанный алгоритм.
Вопросы будут
- Правильно ли это, или я допустил ошибку в своих рассуждениях?
- Какова наихудшая сложность алгоритма?
Сначала бит контекста. Для двух строк определите их сходство как длину самого длинного общего префикса этих двух. Полная самоподобие строки s является суммой сходств s со всеми ее суффиксами. Так, например, полная самоподобие абакаба равна 6 + 0 + 1 + 0 + 2 + 0 = 9, а полная автомодельность повторяющихся n раз составляет n*(n+1)/2.
Описание алгоритма: Алгоритм основан на алгоритме поиска строк Knuth-Morris-Pratt, так как границы строковых префиксов играют центральную роль.
Чтобы воспроизвести: граница строки s является собственной подстрокой b of 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 является нерасширяемой границей длины я + k префикса s. Это граница, потому что это общий префикс s и s[i .. n-1], и если бы он был расширяемым, это был бы не самый длинный общий префикс.
И наоборот, каждая нерасширяемая граница (длины k) префикса длины я s является самым длинным общим префиксом s и суффиксом, начинающимся с s[i-k].
Таким образом, мы можем вычислить полную автомодельность s, суммируя длины всех нерасширяемых границ префиксов длины я s, 1 <= i <= n. Для этого
- Вычислить ширину самых широких границ префиксов на стандартном этапе предварительной обработки KMP.
- Вычислить ширину самых широких не расширяемых границ префиксов.
- Для каждого i,
1 <= i <= n, еслиp = s[0 .. i-1]имеет непустую нерасширяемую границу, пусть b является самым широким из них, добавьте ширину b и для всех непустых границ c из b, если это не растяжимая граница p, добавьте ее длину. - Добавьте длину 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, что уже хорошо. (Очевидно, что в худшем случае квадратично, поэтому ответ "It O (n ^ 2)" интересен только в том случае, если он сопровождается примером квадратичного или почти квадратичного поведения.)
