0

对于以下问题，我很难找到比 O(n^2) 更好的方法。

我得到一个字符串，例如xyxxz.

现在我需要在给定字符串的每个前缀中找到匹配字符的总数。

在这里，字符串的可能前缀是：

 xyxxz : matching characters is 5
 yxxz  : matching characters is 0 (since 1st character doesnt match)
 xxz   : matching characters is 1
 xz    : matching characters is 1
 z     : matching characters is 0

这应该是输出。我做了以下代码：

cin>>str;
len=str.length();
for(i=0;i<len;i++){
    sum=0;
    k=i;
    for(int j=0;j<len;j++)
    {
        if(str[k] == str[j]){
           sum++;
           k++;
        }
        else
            break;
    }
    cout<<sum<<"  ";  //I get the output 5 0 1 1 0
}

但它是 O(n^2)。我想要一个更好的方法：可能是 O(n) 或 O(nlogn)。

提前致谢。

4

5 回答 5

2

这可以使用以下过程在线性时间内完成：

  1. 构造后缀数组 SA 以及 LCP 数组（最长公共前缀数组）。后缀数组是字符串所有后缀的字典排序列表（类似于您在示例中给出的列表，但按字典顺序排序。请注意，每个后缀由其在原始字符串中的起始位置表示，即每个后缀一个整数） . LCP 也是一个整数数组，长度与后缀数组相同。在每个位置 i>0 处，LCP[i] 是后缀数组的第 i 个后缀与第 (i-1) 个后缀共有的最长前缀；我们设置 LCP[0]:=0。

    可以使用 Skew 算法（也称为 DC 算法）在线性时间内构造后缀数组，并且可以在 O(n) 时间内在后缀数组旁边构造 LCP 数组。有关进一步的想法和实现，请参阅有关最先进的后缀数组算法的 SO 帖子。

  2. 确定后缀数组中完整字符串的位置（例如，通过线性扫描后缀数组以查找包含整数 0 的条目）。

  3. 从该位置开始，沿着 LCP 数组向左和向右移动，以识别每个后缀与完整字符串共有的最长前缀。我已经在这个较早的 SO 帖子中详细描述了这个过程。

备注虽然这需要不超过 O(n) 的内存和时间，因此理论上是最优的，但这是一个非常复杂的过程，并且只有在字符串非常长时才会在实践中有用。

于 2012-07-26T05:24:06.003 回答
1

使用后缀数组。后缀数组 DC3 将在 O(N) 时间内完成，其中 N 是原始字符串中的字符数。

于 2013-03-15T05:16:02.303 回答
1

如果为字符串构建后缀树，则可以遍历后缀树以查找匹配项的长度。与第一个字符不匹配的根节点的任何子节点的值都将为零，它的所有后代也是如此。然后，根节点的子节点的所有后代都至少有一个匹配，该匹配等于该边的匹配长度。

于 2012-07-26T04:44:39.513 回答
0

我不擅长计算 O 值。但这是您需要的另一种实现。我觉得效率高一点。

cin >> str;

len=str.length();
for(i=0;i<len;i++)
{
    sum=0;
    k=0;

    while(str[k + sum] == str[i + sum])
    {
            sum++;
    }
    cout << sum ;

}
于 2012-07-26T05:14:29.753 回答
0 
int strcoll (register const char *s1, register const char *s2)
{
    while (*s1 == *s2++) {
        if (*s1++ == '\0') {
            return 0;
        }
    }
    return *s1 - *--s2;
}

此函数开始比较每个字符串的第一个字符。如果它们彼此相等，则继续下一个对，直到字符不同或直到到达表示字符串结尾的空字符。

返回一个整数值，表示字符串之间的关系：零值表示两个字符串相等。大于零的值表示第一个不匹配的字符在 str1 中的值大于在 str2 中的值；小于零的值表示相反。

于 2012-07-26T04:42:09.770 回答