algorithm - 最常见的长度为 X 的子串

Question

我有一个字符串 s，我想搜索在 s 中最常出现的长度为 X 的子字符串。允许重叠子串。

例如，如果 s="aoaoa" 和 X=3，算法应该找到 "aoa"（在 s 中出现 2 次）。

是否存在在 O(n) 时间内执行此操作的算法？

score 8 · Accepted Answer

您可以在 O(n) 时间内使用滚动散列来执行此操作（假设散列分布良好）。一个简单的滚动散列将是字符串中字符的异或，您可以仅使用 2 个异或从先前的子串散列增量计算它。（有关比 xor 更好的滚动哈希，请参阅 Wikipedia 条目。）在 O(n) 时间内使用滚动哈希计算 n-x+1 个子字符串的哈希。如果没有碰撞，答案很明确——如果发生碰撞，你需要做更多的工作。试图弄清楚这是否可以在 O(n) 时间内解决，我的大脑很痛苦。

更新：

这是一个随机的 O(n) 算法。您可以通过扫描哈希表在 O(n) 时间内找到顶部哈希（保持简单，假设没有关系）。使用该散列查找一个 X 长度的字符串（在散列表中保留记录，或者只是重做滚动散列）。然后使用O(n) 字符串搜索算法在 s 中查找该字符串的所有出现。如果您发现与哈希表中记录的出现次数相同，那么您就完成了。

如果没有，那意味着你有一个哈希冲突。选择一个新的随机散列函数，然后重试。如果您的哈希函数具有 log(n)+1 位并且是成对独立的 [ Prob(h(s) == h(t)) < 1/2^{n+1} if s != t]，则 s 中最频繁的 x 长度子字符串与 s 的 <=n 其他长度 x 子字符串发生冲突的概率最多为 1 /2。因此，如果发生冲突，请选择一个新的随机散列函数并重试，您只需一定次数的尝试即可成功。

现在我们只需要一个随机成对独立滚动哈希算法。

更新2：

实际上，您需要 2log(n) 位哈希来避免所有（n 选择 2）冲突，因为任何冲突都可能隐藏正确答案。仍然可行，看起来一般多项式除法的散列应该可以解决问题。

score 4 · Accepted Answer

我看不到在严格的 O(n) 时间内执行此操作的简单方法，除非 X 是固定的并且可以被视为常数。如果 X 是算法的参数，那么执行此操作的最简单方法实际上是 O(n*X)，因为您需要对长度为 X 的子字符串进行比较操作、字符串复制、散列等每次迭代。

（我想象一下，s 是一个多千兆字节的字符串，而 X 是超过一百万的某个数字，并且没有看到任何简单的方法来进行字符串比较或散列长度为 X 的子字符串，即 O (1)，并且不依赖于 X 的大小）

可以通过保留所有内容并避免重新散列整个子字符串来避免在扫描期间复制字符串 - 也许通过使用增量散列算法，您可以一次添加一个字节，并删除最旧的字节- 但我不知道有任何此类算法不会导致需要通过昂贵的后处理步骤过滤掉的大量冲突。

更新

Keith Randall 指出，这种散列称为滚动散列。但是，您仍然必须将每个匹配项的起始字符串位置存储在哈希表中，然后在扫描字符串后验证所有匹配项是否为真。您需要根据为每个哈希键找到的匹配数对可能包含 nX 个条目的哈希表进行排序，并验证每个结果——在 O(n) 中可能不可行。

score 1 · Accepted Answer

它应该是 O(n*m)，其中 m 是列表中字符串的平均长度。对于非常小的 m 值，算法将接近 O(n)

为每个字符串长度构建一个计数哈希表
遍历您的字符串集合，相应地更新哈希表，将当前最流行的数字存储为与哈希表分开的整数变量
完毕。

score 0 · Accepted Answer

Python中的幼稚解决方案

from collections import defaultdict
from operator    import itemgetter

def naive(s, X):
    freq = defaultdict(int)
    for i in range(len(s) - X + 1):
        freq[s[i:i+X]] += 1
    return max(freq.iteritems(), key=itemgetter(1))

print naive("aoaoa", 3)
# -> ('aoa', 2)

用简单的英语

创建映射：长度的子串X-> 它在s字符串中出现的次数
```
for i in range(len(s) - X + 1):
    freq[s[i:i+X]] += 1
```
在映射中找到第二项（频率）最大的对
```
max(freq.iteritems(), key=itemgetter(1))
```

score 0 · Accepted Answer

这是我在 C 中所做的一个版本。希望它有所帮助。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
    char *string = NULL, *maxstring = NULL, *tmpstr = NULL, *tmpstr2 = NULL;
    unsigned int n = 0, i = 0, j = 0, matchcount = 0, maxcount = 0;

    string = "aoaoa";
    n = 3;

    for (i = 0; i <= (strlen(string) - n); i++) {
        tmpstr = (char *)malloc(n + 1);
        strncpy(tmpstr, string + i, n);
        *(tmpstr + (n + 1)) = '\0';
        for (j = 0; j <= (strlen(string) - n); j++) {
            tmpstr2 = (char *)malloc(n + 1);
            strncpy(tmpstr2, string + j, n);
            *(tmpstr2 + (n + 1)) = '\0';
            if (!strcmp(tmpstr, tmpstr2))
                matchcount++;
        }
        if (matchcount > maxcount) {
            maxstring = tmpstr;
            maxcount = matchcount;
        }
        matchcount = 0;
    }

    printf("max string: \"%s\", count: %d\n", maxstring, maxcount);

    free(tmpstr);
    free(tmpstr2);

    return 0;
}

score 0 · Accepted Answer

您可以构建子字符串树。这个想法是像电话簿一样组织您的子字符串。然后查找子字符串并将其计数加一。

在上面的示例中，树将具有以字母开头的部分（节点）：“a”和“o”。'a' 出现 3 次， 'o' 出现两次。所以这些节点的计数分别为 3 和 2。

接下来，在“a”节点下，将出现一个“o”的子节点，对应于子字符串“ao”。这出现了两次。在“o”节点下，“a”也出现了两次。

我们以这种方式继续，直到到达字符串的末尾。

'abac' 的树的表示可能是（同一级别的节点用逗号分隔，子节点在括号中，计数出现在冒号之后）。

a:2(b:1(a:1(c:1())),c:1()),b:1(a:1(c:1())),c:1()

如果树被拉出来，它会更明显！例如，这一切都说明字符串 'aba' 出现一次，或字符串 'a' 出现两次等。但是，存储量大大减少，更重要的是检索速度大大加快（与保留子列表相比）字符串）。

要找出最重复的子字符串，请对树进行深度优先搜索，每次到达叶节点时，记下计数，并跟踪最高的那个。

运行时间可能类似于 O(log(n)) 不确定，但肯定比 O(n^2) 好。

score -1 · Accepted Answer

LZW 算法就是这样做的

这正是 Lempel-Ziv-Welch（用于 GIF 图像格式的 LZW）压缩算法所做的。它找到普遍的重复字节并将它们更改为简短的内容。

维基百科上的 LZW

score -2 · Accepted Answer

在 O(n) 中没有办法做到这一点。

如果你能证明我在这个问题上错了，请随意对我投反对票，但我什么都没有。

algorithm - 最常见的长度为 X 的子串

8 回答 8

Python中的幼稚解决方案

用简单的英语

LZW 算法就是这样做的

Related

Reference