长X的最常见的串(Most common substring of length X)

我有一个字符串s，我想寻找最经常出现在s中长X的字符串。重叠子是允许的。

例如，如果s = “aoaoa” 和X = 3，该算法应该找到 “AOA”（出现2次以s）。

是否一个算法存在，这是否在O（n）的时间？

Answer 1:

你可以使用这样做滚动哈希在O（n）的时间（假设好的哈希分布）。一个简单的滚动哈希将是字符串中的字符的XOR，您可以使用仅2异或之前的子哈希增量计算它。（参见更好的滚动哈希比XOR的维基百科条目。）计算您的N-X + 1个使用滚动散列在O（n）的时间串的哈希值。如果没有冲突，答案是明确的 - 如果碰撞发生，你需要做更多的工作。我的大脑很痛试图找出如果这都可以在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的其他长度×子的碰撞为至多1/2。所以，如果有冲突，选择一个新的随机哈希函数，然后重试，你就只需要尝试固定数量的你成功了。

现在，我们只需要一个随机两两独立滚动散列算法。

UPDATE2：

其实，你需要2log（n）的散列位，以避免所有的（N选2）的碰撞，因为任何碰撞可能隐藏正确的答案。还是可行的，它看起来像由一般多项式除法散列应该做的伎俩。

Answer 2:

我没有看到一个简单的方法在严格O（n）的时间来做到这一点，除非X是固定的，可以被认为是一个常数。如果X是一个参数的算法，这样做的那么最简单的方法实际上是O（N * X），因为你需要做的比较操作，字符串拷贝，哈希等，对在长度X的一个子每次迭代。

（我想象，一分钟，s是一个多千兆字节的字符串，X是超过一百万的一些数字，并没有看到这样做字符串比较，或散列长度X的子串的任何简单的方法，即分别为O （1），并且不依赖于X的大小）

有可能在扫描过程中避免字符串拷贝，在地方留下的一切，以避免重新散列整个子 - 比如用增量哈希算法在那里你可以一次添加一个字节，并删除最旧的字节 - 但我不知道有任何这样的算法，不会导致在需要与昂贵的后处理步骤过滤掉碰撞的巨大的数字。

更新

基思·兰德尔指出，这种哈希被称为滚动哈希 。它仍然存在，虽然，你将不得不存储在您的哈希表中每场比赛的开始字符串的位置，然后扫描你的所有比赛是真实的后弦验证。您将需要排序的哈希表，其中可能包含NX项的基础上，发现每个哈希键匹配的数目，并验证每一个结果 - 可能是在O（n）的不可行。

Answer 3:

它应该是O（N * m），其中m是所述列表中的字符串的平均长度。对于m非常小的值，则算法将接近为O（n）

建立计数的散列表为每个字符串的长度
遍历你的字符串的集合，从哈希表相应地更新哈希表，存储当前最prevelant数字作为整数变量分离
完成。

Answer 4:

在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)) 
```

Answer 5:

LZW算法做到这一点

这正是（以GIF图像格式使用LZW）的Lempel-谢夫 - 韦尔奇压缩算法一样。它发现普遍存在重复字节，并改变他们的东西短。

LZW维基百科

Answer 6:

这里是一个版本，我的确在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;
}