Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
How Many Substrings?
def lcp(s1, s2):
i = 0
while i < len(s1) and i < len(s2) and s1[i] == s2[i]:
i += 1
return i
def get_suffix_array(s):
sub_str = list(s)
suffix_array =[]
for i in range(len(sub_str)):
suffix_array.append(sub_str[i:])
return sorted(suffix_array)
def calculate_distinct_substrings(s):
suffix_array = get_suffix_array(s)
ans = len(suffix_array[0])
for j in range(1, len(suffix_array)):
lcp_value = lcp(suffix_array[j - 1], suffix_array[j])
ans = ans + len(suffix_array[j]) - lcp_value
return ans
n, q = [int(x) for x in input().split()]
s = input()
_dict = dict()
for i in range(q):
left, right = [int(x) for x in input().split()]
sub_str = s[left:right + 1]
if sub_str in _dict.keys():
print(_dict[sub_str])
continue
ans = calculate_distinct_substrings((sub_str))
_dict[sub_str] = ans
print(ans)
# #
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.