長さXの最も頻度の高いサブ

Question

我々は平均O（N）時間の長さNの文字列で、長さXの最も頻繁な部分文字列を見つけるために、どのように長さNの文字列と数のX.

がありますか？私はどのように使用するハッシュ関数の数だけ一定であることを証明するためにお聞きしたいと思いhttps://stackoverflow.com/questions/1597025?tab=votes#tab-top

：私は思う

は、ここで同様の質問です。

Answer 1

suffix treeは、O（n）回の最悪の場合、O（n）スペースの使用でこれを与える必要があります。特に

はΘ（n）は、時間的に最小長さの最も頻繁に発生するサブストリングを探す

言及ストリングサブセクションのプロパティの下に上記WikiページのFunctionalityセクションをチェック。

Answer 2

この種のハッシュ関数をお勧めします。それぞれの文字列が（10ベースではなく）256のベース表記で数値であることをcondiderに許可します。したがって、各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)ただのハッシュテーブルwihtのstd ::マップを変更するために、O(n * log(n))上で動作します。