Count Distinct Substrings

You are provided with a string S. Your task is to determine and return the number of distinct substrings, including the empty substring, of this given string. Implement the solution using a trie data structure.

Input:

First line contains an integer T representing the number of test cases. For each test case, a single line contains the string S.

Output:

Output consists of T lines, each containing an integer result for each test case, representing the number of distinct substrings of string S.

Example:

Input:

2 ab abc

Output:

4 7

Explanation:

For 'ab', distinct substrings are: "", "a", "b", "ab".
For 'abc', distinct substrings are: "", "a", "b", "c", "ab", "bc", "abc".

Constraints:

1

Question

Count Distinct Substrings

You are provided with a string S. Your task is to determine and return the number of distinct substrings, including the empty substring, of this given string. Implement the solution using a trie data structure.

Input:

First line contains an integer T representing the number of test cases. 
For each test case, a single line contains the string S.

Output:

Output consists of T lines, each containing an integer result for each test case, representing the number of distinct substrings of string S.

Example:

Input:

2
ab
abc

Output:

4
7

Explanation:

For 'ab', distinct substrings are: "", "a", "b", "ab".
For 'abc', distinct substrings are: "", "a", "b", "c", "ab", "bc", "abc".

Constraints:

1 <= T <= 5
1 <= |S| <= 10^3
S consists only of lowercase English letters.

Note:

No need to handle printing; this has been managed already. Focus purely on implementing the specified function.

Accepted Answer

Count distinct substrings of a given string using trie data structure.

Implement a trie data structure to store all substrings of the given string.
Count the number of nodes in the trie to get the distinct substrings count.
Handle empty string case separately.
Example: For 'ab', distinct substrings are: '', 'a', 'b', 'ab'.

Asked in Adobe