C++, STL, rolling hash and collision check: true O(n^2) in space and time
I\'ve seen hellishlot many broken rolling-hash-without-collision-check solutions (O(n^2), but really and hopelessly broken, collisions are trivial to find), and
I\'ve seen *hellishlot* many broken rolling-hash-without-collision-check solutions (O(n^2), but *really and hopelessly broken*, collisions are trivial to find), and a lot of (non-broken but slow) solutions claming to be O(n^2), but actually O(n^3) or worse, so I decided to share my solution:\n```c++\nclass Solution {\npublic:\n    int countDistinct(vector<int>& nums, int k, int p) {\n        typedef typename vector<int>::const_iterator iterator;\n        typedef tuple<size_t,iterator,iterator> item_t;\n        // { hash, begin, end }\n\t\t// we save pre-calculated hash value (it MUST match subarray content),\n\t\t// begin and end subarray pointers (iterators);\n        // beware: you must avoid operations invalidating iterators,\n        // or hell break loose\n        struct item_ops {\n            // hash\n            size_t operator() (const item_t& v) const {\n                return get<0>(v); // pre-computed hash value\n            }\n            // equals\n            bool operator() (const item_t&a, const item_t &b) const {\n                return\n                    // same length\n                    distance(get<1>(a), get<2>(a)) == distance(get<1>(b), get<2>(b))\n                    // same content\n                    && equal(get<1>(a), get<2>(a), get<1>(b));\n                // avoid temptation of preliminary optimizations:\n                //  comparing hashes first useless (never happens)\n                //  comparing get<1>(a) and get<1>(b) before equal() is useless\n                //  (we never insert items with both same length and same start)\n            }\n        };\n        // time: O(n^2) (average), space = O(n^2)\n        // Comparison:\n        // 1) unordered<ull> (set of hashes) is prone to collisions, no matter of trick\n\t\t//     and "happy"/"popular"/"large" constants you use;\n        // 2) unordered_set<string> is O(n^3) time and O(n^3) space;\n\t\t// 3) set<vector<int>> is O(n^3 log n) time and O(n^3) space;\n        unordered_set<item_t, item_ops, item_ops> s ((nums.size()+1)*nums.size()/2);\n\t\t// << hints about expected number of items, saves time\n\t\t// and avoids memory fragmentation on resizing hash table\n        for (auto i = nums.cbegin(); i != nums.cend(); ++i) {\n            size_t hash = 0;\n            int t = 0;\n            for (auto j = i; j != nums.cend(); ) {\n                if (*j % p == 0)\n                    if (++t > k)\n                        break;\n                // polynomial hash parameters:\n                //   base = 211 (can be any prime larger than 200)\n                //   modulo = 2**(8*sizeof(size_t)), that is commonly 2**64 (implicit)\n                // you can use any other parameters as you like (e.g. larger base, prime modulo),\n                // or hash combination, etc;\n                // hash collisions here harms performance, but not algorithm correctness\n                hash = 211*hash + *j;\n                ++j;\n\t\t\t\t// end iterator should be one after last subarray element, so just increment it here\n                s.emplace(hash, i, j);\n            }\n        }\n        return s.size();\n    }\n};\n```\nThat said, while it is improvement over commonly-seen O(n^3) (and equally-commonly-seen broken implementations), but there are LCP-based solutions out there, and they are O(n) in both time and space (and unlike any hash-based solution, it is *worst* case performance), so look them up too.
['C', 'Rolling Hash']