所有子字符串的出现频率

Question

我希望能够在C++中查找字符串中所有子字符串的频率。目前我正在使用以下方法：

    unordered_map<string,int> mp;
    string s;// the string of which we want all substrings... n is length
    cin>>s;
    string t;
    for(int i=0,i<=n-1;++i) // starting point of a substring
    {
        t="";
        for(int j=i;j<=n-1;++j) // all substrings startings at i
        {
            t+=s[j];
            ++mp[t];
        }
    }

我想优化它的时间复杂度。有更好的算法吗？抱歉，如果不是这里讨论的话我就关闭它了。

编辑：

这是我想出来的...维护一个包含字符串所有后缀的trie树。然后遍历所有以i为起点的子串，这样搜索就是O(1)。

每个节点都指定一个子字符串（后缀的前缀）。现在在每个节点上维护频率并相应地更新它。虽然这种方法是O(n^2)，但由于内存分配和将下一个指针重置为NULL（26次），所以常数相当大。我能进一步优化它吗？还有比链表更快的存储trie树的替代方法吗？我能够压缩我的解决方案，但很接近时间限制。

- evil999man

---

++mp[v]; 中的 v 是什么？ - tsuki

当你对代码进行性能分析时，哪些行是瓶颈呢？ - Thomas Matthews

什么是上下文？你为什么要这样做？也许有更好的方法。 - Baldrick

在http://codereview.stackexchange.com上发布的帖子应该是正确运行的程序。不要在那里发布代码片段。 - R Sahu

不要删除这个问题。它引发了很好的讨论！ - Brent Washburne

Answer 1

这是原始C代码版本。它使用两个与输入字符串（s_len）长度相同的数组来计算匹配数量和重复位置。优点是字符串在映射中不会被复制，节省了创建映射条目所需的时间（你发现这很慢）。另一个好处是它不需要n^2的内存，像map/reduce函数一样立即输出信息，以便在后续步骤中处理。它使用本地C内存函数，如calloc()、bzero()和memcmp()进行高效的内存分配、清零和比较。

该算法的工作方式如下：

• 对于每个长度为len的字符串，当len从1到s_len-1时：
• 清空数组matches和dups；
• 沿着字符串（使用i）从开始位置（位置0）走到末尾：
• 如果这个位置已经被计算为重复项，则跳过它；
• 对于字符串中更远的每个位置（j=i+1到stop），将其与当前位置进行比较；
• 如果这是一个匹配项，则增加在位置i处的匹配数，并标记位置j为重复项；
• 在此遍历结束时，打印出长度为len的匹配数。

以下是代码:

#include <stdio.h>
#include <stdlib.h>    /* for calloc() */
#include <strings.h>   /* for bzero() */

/* Find the number of matching substrings in the string s */
void sub(char *s)
{
    size_t s_len = strlen(s);
    short *matches = (short *) calloc(s_len, sizeof(short));
    short *dups = (short *) calloc(s_len, sizeof(short));
    size_t n = s_len * sizeof(short);    /* used by bzero() */
    size_t len, i, j, stop;

    /* Find all substrings of length 1..s_len */
    for (len=1; len<s_len; ++len)
    {
        bzero((void *) matches, n);    /* zero out the number of matches */
        bzero((void *) dups, n);       /* zero out the duplicates */
        stop = s_len - len + 1;
        for (i=0; i<stop; ++i)
        {   
            if (dups[i])    /* this is a duplicate (was already counted) */
                continue;   
            for (j=i+1; j<stop; ++j)
            {       
                if (memcmp(s+i, s+j, len))    /* substring comparison */
                    continue;    /* not a match? continue */
                matches[i]++;
                dups[j] = 1;
            }       
            if (matches[i])
                printf("%d: %.*s\n", matches[i]+1, (int) len, s+i);
        }   
    }
}

int main()
{
    sub("abcabcabcabc");
    return 0;
}

这是输出结果：

4: a
4: b
4: c
4: ab
4: bc
3: ca
4: abc
3: bca
3: cab
3: abca
3: bcab
3: cabc
3: abcab
3: bcabc
2: cabca
3: abcabc
2: bcabca
2: cabcab
2: abcabca
2: bcabcab
2: cabcabc
2: abcabcab
2: bcabcabc
2: abcabcabc

- Brent Washburne

Answer 2

这样想一下。假设你的字符串长度为10个字符，而且所有字符都不同：

`0123456789`

在这种情况下，所有的子字符串都是唯一的。因此，有O(n^2)个唯一的子字符串。每个子字符串需要在字典中拥有自己的条目。准确地说，在这种情况下，(n^2)/2 = 50个条目。

因此，将这些子字符串插入字典中至少需要50次插入操作。

因此，在一般情况下，没有太多可以做的来避免O(n^2)的上限。

集中精力使代码本身更快——我不确定你能找到更好的算法。

- Baldrick

---

另外，我现在了解到字符串中的+=操作的时间复杂度与新字符串的大小成线性关系。我们能否在这方面进行改进？ - evil999man

@PhamTrung 我需要阅读后缀树来构建一个O(n^2)算法吗？ - evil999man

@像Baldrick在这里证明的那样，O(n^2)是你能做到的最好的，所以后缀树似乎是你最好的选择之一。 - Pham Trung

@Awesome：直觉上，这似乎是一个后缀树问题，但我还没有看到解决方案。有趣的是，即使后缀树（隐式地）包含O(n^2)个子字符串，你仍然可以在O(n)的时间内构建它。你应该能够利用这一点来创建一个更快的算法。 - rici

你对上限没什么办法。但是不要放弃。如果你处理的是非随机字符串，你可以比上限做得更好。考虑字符串FOODOOFOODOO，一旦你获得了所有FOODOO的子串，你只需要将它们加倍到第二个FOODOO。你不必重新遍历它。 - Rafael Baptista