Определите количество различных подстрок в строке в c ++ и используя хеширование - PullRequest
Новая
       50

Определите количество различных подстрок в строке в c ++ и используя хеширование

3 голосов
/ 12 апреля 2020 
int count_unique_substrings(string const& s) {
    int n = s.size();
    const int p = 31;
    const int m = 1e9 + 9;
    vector<long long> p_pow(n);
    p_pow[0] = 1;

    for (int i = 1; i < n; i++)
        p_pow[i] = (p_pow[i-1] * p) % m;

    vector<long long> h(n + 1, 0);

    for (int i = 0; i < n; i++)
        h[i+1] = (h[i] + (s[i] - 'a' + 1) * p_pow[i]) % m;

    int cnt = 0;

    for (int l = 1; l <= n; l++) {
        set<long long> hs;

        for (int i = 0; i <= n - l; i++) {
            long long cur_h = (h[i + l] + m - h[i]) % m;
            cur_h = (cur_h * p_pow[n-i-1]) % m;  // unable to understand this line (how it works ?)
            hs.insert(cur_h);
        }

        cnt += hs.size();
    }
    return cnt;
}

Проблема в том, что ha sh для подстроки длины l должно быть следующим:

((h [i + l] - h [i]) / p_pow [i])

, но в коде используется:

long long cur_h = (h [i + l] + m - h [i])% m; cur_h = (cur_h * p_pow [ni-1])% m;

Пожалуйста, помогите относительно этого
Спасибо

1 Ответ

1 голос
/ 12 апреля 2020

Если вам нужно только количество подстрок в строке: 

// C++ program to count all distinct substrings in a string 
#include<bits/stdc++.h> 
using namespace std; 

int distinctSubstring(string str) 
{ 
    // Put all distinct substring in a HashSet 
    set<string> result ; 

    // List All Substrings 
    for (int i = 0; i <= str.length(); i++) 
    { 
        for (int j = i + 1; j <= str.length(); j++) 
        { 

            // Add each substring in Set 
            result.insert(str.substr(i, j)); 
        } 
    } 

    // Return size of the HashSet 
    return result.size(); 
} 

// Driver Code 
int main() 
{ 
    string str = "aaaa"; 
    cout << (distinctSubstring(str)); 
}
...