class Solution {
    
    //using rabin karp rolling hash algo to replace text.substring ->O(n) to O(1)
    //which makes the whole algo O(n^2)
    private static final int PRIME = 101;
    private static final int MOD = 1_000_000_007;
    public int distinctEchoSubstrings(String text) {
        /*  Q66 of dp playlist , echo substring(ess)
        */
        
        int n = text.length();
        
        // dp[i][j] : hash value of text[i:j]
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            long hash = 0;
            for (int j = i; j < n; j++) {
                hash = hash * PRIME + (text.charAt(j) - 'a' + 1);
                hash %= MOD;
                dp[i][j] = (int) hash;
            }
        }

        //make a HS to store distinct echo substrings
        HashSet<Integer> set = new HashSet<>();

        //checking all ess of length 2->n/2
        for(int len = 1 ; len <= n/2 ; len++){

            /* we keep checking characters at a gap of length and increasing count
            if chars are equal we keep the count going for potential ess ,if chars
            are not equal our current potential ess is ruined and we start checking
            again for new ess from count = 0

            if count = len , we add the substring in the HS and count-- to check if
            the next characters are making and ess , basically it means deleting
            a character from behind and continue checking to find next ess
            */
            int count = 0;
            for(int i = 0,j = len ;j < n ; i++ , j++){
                
                char ch1 = text.charAt(i) , ch2 = text.charAt(j);

                if(ch1 == ch2)
                count ++;

                else
                count = 0;

                if(count == len){
                //here instead of substring function we store a unique hashvalue for i to jth string in dp
                    set.add(dp[i][j]);
                    count --;
                }
            }
        }
        System.out.print(set);
        return set.size();
    }
}