Describe and analyze an algorithm to find the length of the longest substring that appears both forward and backward in an input string T[1 . n]. The forward and backward substrings must not overlap. Here are several examples:
• Given the input string ALGORITHM, your algorithm should return 0.
• Given the input string RECURSION, your algorithm should return 1, for the substring R.
• Given the input string REDIVIDE, your algorithm should return 3, for the substring EDI.
(The forward and backward substrings must not overlap)
• Given the input string DYNAMICPROGRAMMINGMANYTIMES, your algorithm should return 4, for the substring YNAM
The algorithm should run in O(n2) time.