Answer:
Here is the Python program to compute how many distinct substrings of a string s are palindromes:
def AllPalindromes(s, l, h, sub): #function that finds all the palindromes
while l >= 0 and h < len(s) and s[l] == s[h]: #the loop iterates and reads the s until s[l.h] is a palindrome
sub.add(s[l: h + 1]) #adds the palindromes to sub
l = l - 1 #decrements the count of l by 1
h = h + 1 #increments the count of h by 1
def DistinctPalindromes(s): #function to find all distinct palindromic substrings of s and also their number
substr = set() #stores all distinct substrings of s which are palindromes
for i in range(len(s)): #iterates through s
AllPalindromes(s, i, i,substr) # find all palindromes with odd length and with s[i] as mid point
AllPalindromes(s, i, i + 1, substr) # find all palindromes with even length and with s[i] as mid point
print("palindromic substrings are",substr, '\\',end='') # display all distinct palindromic substrings
print(len(substr),"distinct substrings of",s,"are palindromes") # display the number of distinct palindromic substrings
print("Enter a string:") #prompts user to enter a string
s = input() #accepts input from user
DistinctPalindromes(s) #calls DistinctPalindromes method by passing input string to it in order to compute the
Step-by-step explanation:
The program is well explained in the comments attached with each statement of the code. The function AllPalindromes finds all the palindromes of string s. while loop iterates and reads the string forward and backward to find same i.e. palindrome. Here h and l represents high and low part of the string s. They can also be called as forward and backward pointers to the s characters. The while condition also checks the characters at s[l] position in the string s is equal to the character at s[h]. add() method is used to push all palindromes into the set sub. The function DistinctPalindromes is used to find all the distinct substrings of s that are palindromes. The loop iterates through characters of string s and calls AllPalindromes method to find all palindromes with odd and even length. It then prints the distinct palindromic substrings . For examples s = "aabaa" then the palindromic substrings are {'aabaa', 'b', 'aba', 'a', 'aa'} and the number of distinct substrings of aabaa that are palindromes is 5. The program along with its output is attached in a screenshot.