c++ - 字符串中的子串计算

Question

对于以下问题，我很难找到比 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)。

提前致谢。

Answer 1

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

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

   可以使用 Skew 算法(也称为 DC 算法)在线性时间内构造后缀数组，并且可以在 O(n) 时间内与后缀数组一起构造 LCP 数组。查看 SO post on state-of-the-art suffix array algorithms进一步的想法和实现。

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

3. 从该位置开始，沿着 LCP 数组向左和向右移动，以确定每个后缀与完整字符串共有的最长前缀。我在 this older SO post 中详细描述了这个过程.

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