Leetcode-Solutions/Distinct Echo Substrings at master · shivammaniharsahu/Leetcode-Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
public:
    int distinctEchoSubstrings(string text)
    {
       int n=text.size();
        long long hash[n][n];
        int mod=1e9+7;
        unordered_map<long long,int> MP;

        for(int i=0;i<n;i++)
        {
            long long pow=31;
            hash[i][i]=pow*(text[i]-'a'+1);
            for(int j=i+1;j<n;j++)
            {
                pow=(pow*31)%mod;
                hash[i][j]=(hash[i][j-1]%mod+pow*(text[j]-'a'+1)%mod)%mod;
            }
        }

        int ans=0;
        for(int i=0;i<n;i++)
        {
            for(int j=i;j<n;j++)
            {
                int sz=j-i+1;
                if(j+sz>=n) continue;
                if(hash[i][j]==hash[j+1][j+sz])
                {
                    if(MP[hash[i][j]]==0) ans++;
                    MP[hash[i][j]]++;
                }
            }
        }
        return ans;
    }
};