Самая частая подстрока длины X

Question

У нас есть строка длины N и число X.

Как найти наиболее частую подстроку длины X в строке длины N за среднее время O (N)?

Я думаю, вот похожий вопрос: https://stackoverflow.com/questions/1597025?tab=votes#tab-top

Я хотел бы спросить вас, как доказать, что число используемых хеш-функций является только константой.

Answer 1

A дерево суффиксов должно давать это в O (n) наихудшем случае при использовании O (n) пространства.

В частности, проверьте секцию Функциональность вышеупомянутой вики-страницы в подразделе Свойства строк, в котором упоминается

Найти наиболее часто встречающиеся подстроки минимальной длины за время Θ (n).

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)), чтобы сделать его O(n), просто измените std :: map с любой хеш-таблицей.