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".

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



def countDistinctSubstring(s):

    #code here



Solutions:
def countDistinctSubstring(s):
	n = len(s)
	st = set()
	for i in range(n):
		res = ''
		for j in range(i, n):
			res += s[j]
			st.add(res)
	return len(st) + 1


def countDistinctSubstring(s):
	se = set()
	se.add('')
	se.add(str(s[0]))
	for i in range(1, len(s)):
		se.add(str(s[i]))
		for j in range(i):
			se.add(str(s[j:i + 1]))
			se.add(str(s[j]))
	return len(se)


def countDistinctSubstring(s):
	str = {}
	c = 1
	for i in range(len(s)):
		for j in range(i, len(s)):
			if s[i:j + 1] not in str:
				str[s[i:j + 1]] = 1
				c += 1
	return c


class trieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEnd = False

class Trie:

	def __init__(self):
		self.root = trieNode()
		self.cnt = 0

	def insert(self, word):
		r = self.root
		for i in word:
			if r.children[ord(i) - ord('a')] == None:
				r.children[ord(i) - ord('a')] = trieNode()
				self.cnt += 1
			r = r.children[ord(i) - ord('a')]

def countDistinctSubstring(s):
	dct = dict()
	for i in range(1, len(s) + 1):
		for j in range(i):
			if s[j:i] not in dct:
				dct[s[j:i]] = 1
	return len(dct) + 1


def countDistinctSubstring(s):
	res = [s[i:j] for i in range(len(s)) for j in range(i + 1, len(s) + 1)]
	set1 = set()
	for i in res:
		set1.add(i)
	return len(set1) + 1


def countDistinctSubstring(s):
	ans = set()
	for i in range(len(s)):
		ss = ''
		for j in range(i, len(s)):
			ss += s[j]
			ans.add(ss)
	ans_len = len(ans)
	return ans_len + 1


def countDistinctSubstring(s):
	if len(s) == 1:
		return 2
	ans = set()
	for i in range(len(s)):
		for j in range(len(s)):
			ans.add(s[i:j + 1])
	return len(ans)


def countDistinctSubstring(s):
	k = 1
	p = set()
	for i in range(len(s)):
		for j in range(i + 1, len(s) + 1):
			p.add(s[i:j])
	return len(p) + 1


def countDistinctSubstring(s):
	ans = set()
	for i in range(len(s)):
		k = 0
		for j in range(i, len(s)):
			ans.add(s[k:j + 1])
			k += 1
	return len(ans) + 1


def countDistinctSubstring(s):
	subit = set()
	for i in range(len(s)):
		for j in range(i + 1, len(s) + 1):
			subit.add(s[i:j])
	return len(subit) + 1


def countDistinctSubstring(s):
	uniq = set('')
	for i in range(len(s)):
		ss = ''
		for j in range(i, len(s)):
			ss = ss + s[j]
			uniq.add(ss)
	return len(uniq) + 1


def countDistinctSubstring(s):
	ans = set()
	n = len(s)
	for window in range(n):
		i = 0
		for j in range(window, n):
			ans.add(s[i:j + 1])
			i += 1
	return len(ans) + 1


def countDistinctSubstring(s):
	a = set()
	n = len(s)
	for i in range(n):
		p = 0
		for j in range(i, n):
			a.add(s[p:j + 1])
			p += 1
	return len(a) + 1


from itertools import combinations

def countDistinctSubstring(s):
	l = []
	for i in range(len(s)):
		for j in range(i, len(s) + 1):
			l.append(s[i:j])
	return len(set(l))


class TrieNode:

	def __init__(self):
		self.links = {}

class Trie:

	def __init__(self):
		self.root = TrieNode()

def countDistinctSubstring(s):
	ans = set()
	n = len(s)
	for window in range(n):
		i = 0
		for j in range(window, n):
			ans.add(s[i:j + 1])
			i += 1
	return len(ans) + 1


def countDistinctSubstring(s):
	d = {}
	cnt = 1
	for i in range(len(s)):
		for j in range(i + 1, len(s) + 1):
			a = s[i:j]
			if a not in d:
				d[a] = 1
				cnt += 1
	return cnt


def countDistinctSubstring(s):
	m = {}
	n = len(s)
	for i in range(n):
		t = s[i]
		m[s[i]] = 1
		for j in range(i + 1, n):
			t += s[j]
			m[t] = 1
	return len(m) + 1


def countDistinctSubstring(s):
	se = set()
	n = len(s)
	for i in range(n):
		cur = ''
		for j in range(i, n):
			cur += s[j]
			se.add(cur)
	return len(list(se)) + 1


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfString = False

def countDistinctSubstring(s):
	count = 1
	substrings = {}
	for i in range(len(s)):
		for j in range(i, len(s)):
			if s[i:j + 1] not in substrings:
				substrings[s[i:j]] = 1
				count += 1
	return count


class Trie:

	def __init__(self):
		self.root = {}

	def addAndCount(self, word):
		curr = self.root
		count = 0
		for c in word:
			if c not in curr:
				curr[c] = {}
				count += 1
			curr = curr[c]
		return count

def countDistinctSubstring(s):
	count = 0
	trie = Trie()
	for i in range(len(s)):
		count += trie.addAndCount(s[i:])
	return count + 1


from collections import defaultdict

class Trie:

	def __init__(self):
		self.child = defaultdict(Trie)

	def insert(self, i, word):
		cnt = 0
		cur = self
		for j in range(i, len(word)):
			if word[j] not in cur.child:
				cnt += 1
			cur = cur.child[word[j]]
		return cnt

def countDistinctSubstring(s):
	ans = set()
	n = len(s)
	for window in range(n):
		i = 0
		for j in range(window, n):
			ans.add(s[i:j + 1])
			i += 1
	return len(ans) + 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		print(countDistinctSubstring(s))


def countDistinctSubstring(s):
	ans = set()
	for i in range(len(s)):
		temp = ''
		for j in range(i, len(s)):
			temp += s[j]
			ans.add(temp)
	return len(ans) + 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		print(countDistinctSubstring(s))


class TrieNode:

	def __init__(self):
		self.rels = {}

	def add(self, key):
		if key in self.rels:
			return
		self.rels[key] = TrieNode()

	def get(self, key):
		return self.rels.get(key)

	def has(self, key):
		return key in self.rels

def countDistinctSubstring(s):
	us = set()
	for i in range(len(s)):
		ss = ''
		for j in range(i, len(s)):
			ss = ss + s[j]
			us.add(ss)
	return len(us) + 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		s = input()
		print(countDistinctSubstring(s))


def countDistinctSubstring(s):
	n = len(s)
	l = set()
	for i in range(n):
		sub = ''
		for j in range(i, n):
			sub += s[j]
			l.add(sub)
	return 1 + len(l)


def countDistinctSubstring(s):
	res = set()
	n = len(s)
	for x in range(n):
		i = 0
		for j in range(x, n):
			res.add(s[i:j + 1])
			i += 1
	return len(res) + 1


def countDistinctSubstring(s):
	N = len(s)
	Set = set()
	Set.add('')
	for window in range(N):
		for j in range(window, N):
			Set.add(s[window:j + 1])
	return len(Set)


def countDistinctSubstring(s):
	tmp = set()
	n = len(s)
	for i in range(n):
		k = 0
		for j in range(i, n):
			tmp.add(s[k:j + 1])
			k += 1
	return len(tmp) + 1


def solution1(s):
	n = len(s)
	ss = set()
	ss.add('')
	count = 1
	for i in range(n):
		sub = s[i]
		if sub not in ss:
			ss.add(sub)
			count += 1
		for j in range(i + 1, n):
			sub += s[j]
			if sub not in ss:
				ss.add(sub)
				count += 1
	return count

def countDistinctSubstring(s):
	return solution1(s)


def countDistinctSubstring(s):
	l = []
	if len(s) == 1:
		return 2
	for i in range(len(s)):
		for j in range(len(s)):
			ss = s[i:j + 1]
			l.append(ss)
	se = set(l)
	return len(se)


def countDistinctSubstring(s):
	Set = set()
	for i in range(len(s)):
		string = ''
		for j in range(i, len(s)):
			string += s[j]
			Set.add(string)
	return len(Set) + 1


def countDistinctSubstring(a):
	count = 0
	l = []
	for i in range(len(s)):
		for j in range(i + 1, len(s) + 1):
			l.append(a[i:j])
	return len(set(l)) + 1


class node:

	def __init__(self):
		self.c = {}
		self.end = False

class Trie:

	def __init__(self):
		self.r = node()

	def insert(self, word):
		ans = 0
		iter = self.r
		for c in word:
			if c not in iter.c:
				iter.c[c] = node()
				ans += 1
			iter = iter.c[c]
			iter.end = True
		return ans

def countDistinctSubstring(s):
	ans = set()
	n = len(s)
	for window in range(n):
		i = 0
		for j in range(window, n):
			ans.add(s[i:j + 1])
			i += 1
	return len(ans) + 1


class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndofword = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

def is_present(root, text):
	curr_node = root
	for char in text:
		index = ord(char) - ord('a')
		if not curr_node.children[index]:
			return False
		curr_node = curr_node.children[index]
	return True

def insert(root, text, unique_count):
	curr_node = root
	for char in text:
		index = ord(char) - ord('a')
		if not curr_node.children[index]:
			curr_node.children[index] = TrieNode()
			unique_count[0] += 1
		curr_node = curr_node.children[index]

def countDistinctSubstringTrie1(s):
	c_trie = Trie()
	unique_count = 1
	num_chars = len(s)
	for i in range(num_chars):
		for j in range(i, -1, -1):
			sub_str = s[j:i + 1]
			print(sub_str)
			if not is_present(c_trie.root, sub_str):
				insert(c_trie.root, sub_str)
				unique_count += 1
	return unique_count

def countDistinctSubstringTrie2(s):
	c_trie = Trie()
	unique_count = [1]
	num_chars = len(s)
	for i in range(num_chars):
		insert(c_trie.root, s[i:], unique_count)
	return unique_count[0]

class Suffix:

	def __init__(self, index):
		self.index = index
		self.first_rank = None
		self.second_rank = None

def get_suffix_arr(text):
	n = len(text)
	suffix_list = [Suffix(i) for i in range(n)]
	previous_rank = [ord(text[i]) - ord('a') for i in range(n)]
	k = 1
	while k <= n:
		for i in range(n):
			curr_index = suffix_list[i].index
			suffix_list[i].first_rank = previous_rank[curr_index]
			kth_index = curr_index + k
			suffix_list[i].second_rank = previous_rank[kth_index] if kth_index < n else -1
		suffix_list.sort(key=lambda x: (x.first_rank, x.second_rank))
		for i in range(n):
			curr_suffix = suffix_list[i]
			prev_suffix = suffix_list[i - 1] if i - 1 > -1 else None
			if prev_suffix and curr_suffix.first_rank == prev_suffix.first_rank and (curr_suffix.second_rank == prev_suffix.second_rank):
				previous_rank[curr_suffix.index] = previous_rank[prev_suffix.index]
			else:
				previous_rank[curr_suffix.index] = i
		k *= 2
	return [x.index for x in suffix_list]

def get_lcp(text):
	n = len(text)
	suffix_arr = get_suffix_arr(text)
	inverse_arr = [0] * n
	lcp = [0] * n
	for i in range(n):
		str_index = suffix_arr[i]
		inverse_arr[str_index] = i
	k = 0
	for i in range(n):
		suffix_index = inverse_arr[i]
		if suffix_index + 1 > n - 1:
			k = 0
			lcp[suffix_index] = k
			continue
		str_index_i = i
		str_index_j = suffix_arr[suffix_index + 1]
		while str_index_i + k < n and str_index_j + k < n and (text[str_index_i + k] == text[str_index_j + k]):
			k += 1
		lcp[suffix_index] = k
		if k > 0:
			k -= 1
	return (lcp, suffix_arr)

def countDistinctSubstring(s):
	n = len(s)
	(lcp, suffix_arr) = get_lcp(s)
	count = 1
	for i in range(n):
		count += n - suffix_arr[i] - (lcp[i - 1] if i - 1 > -1 else 0)
	return count


def countDistinctSubstring(s):
	subs = []
	for i in range(0, len(s)):
		for j in range(i, len(s)):
			subs.append(s[i:j + 1])
	s = set(subs)
	return len(s) + 1