Longest Palindromic Substring

1. Given a string, find the longest substring which is palindrome.

Submit the problem as a file longestPalindrome.pl. It should contain a predicate: longestPalindrome(+L1,-L2)/2 of 2 arguments of the type list that returns in the second argument the longest sublist which is a palindrome.

Note that double quoted strings in XSB Prolog are lists of their Unicodes, e.g., "Hello" = [72,101,108,108,111].

Your program should work under XSB Prolog as follows:

xsb -e "[longestPalindrome], longestPalindrome("I have a cool racecar. It is a civic. I got it at noon. Its rotor beats any radar. Other palindromic words: madam, level, kayak, refer.", L2), write(L2), halt."

L2=[114,97,99,101,99,97,114]

There are multiple methods to implement this problem.

Method 1 ( Brute Force ) The simple approach is to check each substring whether the substring is a palindrome or not. We can run three loops, the outer two loops pick all substrings one by one by fixing the corner characters, the inner loop checks whether the picked substring is palindrome or not.

Time complexity: O ( n^3 )

Method 2 ( Dynamic Programming ) The time complexity can be reduced by storing results of subproblems. The idea is similar to this post. We maintain a boolean table[n][n] that is filled in bottom up manner. The value of table[i][j] is true, if the substring is palindrome, otherwise false. To calculate table[i][j], we first check the value of table[i+1][j-1], if the value is true and str[i] is same as str[j], then we make table[i][j] true. Otherwise, the value of table[i][j] is made false.