Problem statement

https://binarysearch.com/problems/Distinct-Substrings/

Solution

Equal to Leetcode 1698 Number of Distinct Substrings in a String.

Complexity

It is O(n^2) for time and O(n) for space.

Code

class Solution:
    def solve(self, s):
        def RabinKarp(text, M, q):
            h, t, d = (1<<(8*M-8))%q, 0, 256
            ans = set()

            for i in range(M): 
                t = (d * t + ord(text[i]))% q
            
            ans.add(t)

            for i in range(len(text) - M):
                t = (d*(t-ord(text[i])*h) + ord(text[i + M]))% q
                ans.add(t)
            return len(ans)
        
        q = (1<<64) - 179
        ans = 0
        for i in range(1, len(s) + 1):
            ans += RabinKarp(s, i, q)
            
        return ans