4 Scripta Manent

Professor Archeoscriptus is working on some old scripts. In particular he is interested in identifying words that are the same whether read from right to left or from left to right, e.g. . Your task is to devise an algorithm that helps the professor identify the longest of all such words that are a subsequence of a given sequence of letters x[1..n].

Hint: You may want to look at T(i,j) = length of longest word that is subsequence of x[i..j].

// Instructions: For this problem, you should argue the correctness of the algorithm, and analyze the order of running time. Please propose algorithms that are as efficient as possible. You will not get more than 2 points per problem for brute-force solutions.