Description

Submission

class Solution {
public:
    int countDistinct(string s) {
        int n = s.length();
        uint64_t base = 26;
        uint64_t power = 1;
        int ret = 0;
        for(int len = 1; len <= n; ++len) {
            power *= base;
            unordered_set<uint64_t> hashes;
            uint64_t h = 0;
            for(int i = 0; i < n; ++i) {
                h = h * base + (s[i] - 'a');
                if(i >= len) h = h - (s[i-len] - 'a') * power;
                if(i >= len - 1) hashes.insert(h);
            }
            ret += hashes.size();
        }
        return ret;
    }
};


// for each length. -- n
//  for each substring of certain length -- n
//   count the number of hashes

// O(n^2)