非常に大きな部分文字列を衝突なく素早くハッシュするには？

Question

私は、その一部として入力文字列のすべてのパリンドローム部分文字列を見つけるアプリケーションを持っています。入力文字列の長さは最大100,000であるため、部分文字列は非常に大きくなる可能性があります。例えば、アプリケーションへの1つの入力は10,000の長さを超える300,000を超える部分文字列の回文をもたらした。このアプリケーションは後ですべての回文を等価でカウントし、回文を見つける関数で行われる標準ハッシュを使用するハッシュで一意のものを数えます。ハッシュはベクトルに格納され、後でアプリ内での一意性のためにカウントされます。そのような入力および出力状態の問題は、非常に長い部分文字列が長すぎてハッシュの衝突を取得するためのハッシュです。だから、非常に大きな部分文字列を素早く一意にハッシュできるアルゴリズム（ハッシュ）があるかどうか疑問に思っていました。ハッシングは、関数get_palinsの終わりに行われます。コードは以下の通りです。問題Xに直面し

#include <iostream> 
#include <string> 
#include <cstdlib> 
#include <time.h> 
#include <vector> 
#include <algorithm> 
#include <unordered_map> 
#include <map> 
#include <cstdio> 
#include <cmath> 
#include <ctgmath> 

using namespace std; 

#define MAX 100000 
#define mod 1000000007 

vector<long long> palins[MAX+5]; 

// Finds all palindromes for the string 
void get_palins(string &s) 
{ 
    int N = s.length(); 
    int i, j, k, // iterators 
    rp,  // length of 'palindrome radius' 
    R[2][N+1]; // table for storing results (2 rows for odd- and even-length palindromes 

    s = "@" + s + "#"; // insert 'guards' to iterate easily over s 

    for(j = 0; j <= 1; j++) 
    { 
     R[j][0] = rp = 0; i = 1; 

     while(i <= N) 
     { 
      while(s[i - rp - 1] == s[i + j + rp]) { rp++; } 
      R[j][i] = rp; 
      k = 1; 
      while((R[j][i - k] != rp - k) && (k < rp)) 
      { 
       R[j][i + k] = min(R[j][i - k],rp - k); 
       k++; 
      } 
      rp = max(rp - k,0); 
      i += k; 
     } 
    } 

    s = s.substr(1,N); // remove 'guards' 

    for(i = 1; i <= N; i++) 
    { 
     for(j = 0; j <= 1; j++) 
      for(rp = R[j][i]; rp > 0; rp--) 
      { 
       int begin = i - rp - 1; 
       int end_count = 2 * rp + j; 
       int end = begin + end_count - 1; 
       if (!(begin == 0 && end == N -1)) 
       { 
        string ss = s.substr(begin, end_count); 
        long long hsh = hash<string>{}(ss); 
        palins[begin].push_back(hsh); 

       } 
      } 
    } 
} 
unordered_map<long long, int> palin_counts; 
unordered_map<char, int> end_matches; 

// Solve when at least 1 character in string is different 
void solve_all_not_same(string &s) 
{ 
    int n = s.length(); 
    long long count = 0; 

    get_palins(s); 

    long long palin_count = 0; 

    // Gets all palindromes into unordered map 
    for (int i = 0; i <= n; i++) 
    { 
     for (auto& it : palins[i]) 
     { 
      if (palin_counts.find(it) == palin_counts.end()) 
      { 
       palin_counts.insert({it,1}); 
      } 
      else 
      { 
       palin_counts[it]++; 
      } 
     } 
    } 

    // From total palindromes, get proper border count 
    // minus end characters of substrings 
    for (auto it = palin_counts.begin(); it != palin_counts.end(); ++it) 
    { 
     int top = it->second - 1; 

     palin_count += (top * (top + 1))/2; 
     palin_count %= mod; 
    } 

    // Store string character counts in unordered map 
    for (int i = 0; i <= n; i++) 
    { 
     char c = s[i]; 

     //long long hsh = hash<char>{}(c); 

     if (end_matches[c] == 0) 
      end_matches[c] = 1; 
     else 
      end_matches[c]++; 

    } 

    // From substring end character matches, get proper border count 
    // for end characters of substrings 
    for (auto it = end_matches.begin(); it != end_matches.end(); it++) 
    { 
     int f = it->second - 1; 
     count += (f * (f + 1))/2; 
    } 

    cout << (count + palin_count) % mod << endl; 

    for (int i = 0; i < MAX+5; i++) 
     palins[i].clear(); 
} 

int main() 
{ 

    string s; 
    cin >> s; 

    solve_all_not_same(s); 

    return 0; 
} 

Answer 1

（はすべて回文サブストリングを見つける）、あなたはY（ハッシュストリング迅速）を解決する方法を尋ねる：The XY Problemを。
回文検出の場合、接尾辞配列を考慮してください（1つは入力の逆、または入力に追加されます）。
重複する文字列を高速にハッシュする場合は、rolling hashesを参照してください。