def longest_palindromic_substring(s):
    res = [0, 0]

    n = len(s)
    dp = [[False for i in range(len(s))] for i in range(len(s))]
    
    for i in range(len(s)):
        dp[i][i] = True

    for i in range(len(s)-1):
        dp[i][i + 1] = (s[i] == s[i + 1])
        if dp[i][i + 1]:
            res = [i, i + 1]

    for length in range(3, len(s)+1):
        i = 0
        for j in range(length - 1, len(s)):
            dp[i][j] = dp[i + 1][j - 1] and (s[i] == s[j])
            if dp[i][j]:
                res = [i, j]
            i += 1
    
    return s[res[0]:res[1] + 1]

# Driver code
def main():
    strings = ['cat', 'lever', 'xyxxyz', 'wwwwwwwwww', 'tattarrattat']
    
    for i in range(len(strings)):
        print(i + 1, ".\t Input string: '", strings[i], "'", sep="")
        result = longest_palindromic_substring(strings[i])
        print("\t Number of palindromic substrings: ", result, sep="")
        print("-" * 100)
    
if __name__ == '__main__':
    main()