这个算法是线性的吗？
受这两个问题的启发：String manipulation: calculate the "similarity of a string with its suffixes"和Program execution varies as the I/P size increases beyond 5 in C，我提出了以下算法。
问题是
reasoning?
- What是算法中最糟糕的情况，
- 是正确的吗？
先介绍一下背景。对于两个字符串，将它们的相似性定义为两个字符串最长的公共前缀的长度。字符串s的总自相似性是s与其所有后缀的相似性之和。例如，abacab的总自相似性为6+0+1+0+2+0=9，重复n次数的总自相似性为n*(n+1)/2。
算法描述：算法是基于Knuth Pratt字符串搜索算法，在字符串的边界前缀中起着核心作用。
概括一下:字符串s的边框是s的一个适当的子字符串b，它同时是一个前缀和一个s的后缀。
注:如果b和c是s的边界，b比c短，那么b也是c的边界，反之，c的每一个边界也是s的边界。
设一个长度为n的字符串，p为长度为i的s的前缀。如果是i == n或s[i] != s[k]，则称为宽度k的边框b，否则它是可扩展的(s的长度k+1前缀是s的长度i+1前缀的边框)。
现在，如果s的最长的公共前缀和以s[i], i > 0开头的后缀有长度k，那么s的长度k前缀是s的长度i+k前缀的不可扩展边框，因为它是s和s[i .. n-1]的公共前缀，如果它是可扩展的，它将不是最长的公共前缀。
相反，s的长度i前缀的每个不可扩展边框(长度k)都是s的最长公共前缀，后缀以s[i-k]开头。
因此，我们可以通过求和s，1 <= i <= n的长度i前缀的所有不可扩展边界的长度来计算s的总自相似性。做那件事
根据标准KMP预处理step.
- Calculate计算前缀最宽边框的宽度prefixes.
- For i，
1 <= i <= n的最宽不可扩展边框的宽度，如果p = s[0 .. i-1]具有非空不可扩展边框，则b是其中最宽的，将b的宽度加上b的所有非空边框c，如果它是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))，那就太好了。(在最坏的情况下，它显然是二次型的，所以"It's O(n^2)“的答案只有在有一个关于二次或近二次行为的例子时才是有趣的。)
回答 2
Stack Overflow用户
发布于 2012-02-15 20:39:46
这看起来是一个非常好的主意，但遗憾的是，我认为最坏的情况是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_bordersi对i的(2K+1)值等于K。
( 2)对于0<=j<=K，边界j=j-1
3)算法中的最后一个循环将使用j==K进入内环，以获取i的2K+1值。
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次！
也许有一种方法可以修正这种情况下的算法？
Stack Overflow用户
发布于 2011-12-19 22:14:46
您可能想看看Z-算法，这显然是线性的：
S是长度为N的C-字符串。
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的条目之和。
https://stackoverflow.com/questions/8563336
复制相似问题
腾讯云开发者
