Count of distinct substrings Using Tries

 Given a string of length N of lowercase alphabet characters. The task is to complete the function countDistinctSubstring(), which returns the count of total number of distinct substrings of this string.

Input:

The first line of input contains an integer T, denoting the number of test cases. Then T test cases follow. Each test case contains a string str.

Output:

For each test case in a new line, output will be an integer denoting count of total number of distinct substrings of this string.

User Task:

Since this is a functional problem you don't have to worry about input, you just have to complete the function countDistinctSubstring().

Constraints:

1 ≤ T ≤ 10

1 ≤ N ≤ 1000

Example(To be used only for expected output):

Input:

2

ab

ababa

Output:

4

10

Exaplanation:

Testcase 1: For the given string "ab" the total distinct substrings are: "", "a", "b", "ab".

class GfG {

    // Inner static TrieNode class

    static class TrieNode {

        TrieNode[] children = new TrieNode[26];

    }

    // Insert a suffix and count how many new nodes (distinct substrings) it adds

    public static int substringCount(String str, TrieNode root) {

        TrieNode current = root;

        int count = 0;

        for (char ch : str.toCharArray()) {

            int index = ch - 'a';

            if (current.children[index] == null) {

                current.children[index] = new TrieNode();

                count++;

            }

            current = current.children[index];

        }

        return count;

    }

    // Main method to count all distinct substrings

    public static int countDistinctSubstring(String st) {

        TrieNode root = new TrieNode();

        int total = 0;

        for (int i = 0; i < st.length(); i++) {

            String suffix = st.substring(i); // ✅ Fixed variable name

            total += substringCount(suffix, root); // ✅ Fixed method name

        }

        return total + 1; // +1 to count the empty string

    }

}