长度为X的最常见子字符串

Question

我们有一个长度为N和数字X的字符串。

如何在平均O（N）时间内找到长度为X的字符串中出现最频繁的子字符串？

我认为这里有一个类似的问题：https://dev59.com/8knSa4cB1Zd3GeqPR-Sy?tab=votes#tab-top 我想问你如何证明使用的哈希函数数量只是一个常数。

- Thomas

---

链接的问题被标记为“作业” - 我只能假设这也是。 - Oded

这个回答解决了你的问题吗？长度为X的最常见子串 - qwr

Answer 1

一个后缀树应该在最坏情况下以O(n)的时间复杂度，使用O(n)的空间。

特别是在上述维基页面的功能部分下，在字符串子部分的属性中检查，其中提到

在Θ(n)时间内找到最常出现的最小长度子字符串。

- Aryabhatta

Answer 2

我建议使用这种哈希函数。假设每个字符串都是以256进制表示的数字（而不是我们通常用的10进制）。因此，对于每个长度为X的子字符串，我们可以通过以下方式将其转换为10进制数值：

#include <iostream>
#include <string>
#include <map>
#include <algorithm>


int main()
{
    std::string s;
    int x;
    std::cin >> s >> x;

    unsigned const int base = 256;
    unsigned long long xPowOfBase = 1;
    int i = 0;
    for(i = 1; i <= x; ++i)
        xPowOfBase *= base;

    unsigned long long firstXLengthSubString = 0;
    for(i = 0; i < x; ++i)
    {
        firstXLengthSubString *= base;
        firstXLengthSubString += s[i];
    }

    unsigned long long nextXLengthSubstring = firstXLengthSubString;

    std::map<unsigned long long, std::pair<int, int> > hashTable;
    for(;i <= s.size(); ++i)
    {
        if(hashTable.find(nextXLengthSubstring) != hashTable.end())
            ++hashTable[nextXLengthSubstring].first;
        else
            hashTable.insert(std::make_pair(nextXLengthSubstring, std::make_pair(1, i - x)));

        if(i != s.size())
        {
            nextXLengthSubstring *= base;
            nextXLengthSubstring += s[i];
            nextXLengthSubstring -= s[i - x] * xPowOfBase;
        }
    }

    std::map<unsigned long long, std::pair<int, int> >::iterator it = hashTable.begin();
    std::map<unsigned long long, std::pair<int, int> >::iterator end_it = hashTable.end();
    std::pair<int, int> maxCountAndFirstPosition = std::make_pair(0, -1);

    for(;it != end_it; ++it)
    {
        if(maxCountAndFirstPosition.first < it->second.first)
            maxCountAndFirstPosition = it->second;
    }

    std::cout << maxCountAndFirstPosition.first << std::endl;
    std::cout << s.substr(maxCountAndFirstPosition.second, x) << std::endl;
    return 0;
}

这将在 O(n * log(n)) 上运行，如果使用任何哈希表替换 std::map，则可以使其变为 O(n)。

- Mihran Hovsepyan