# Longest palindrome subsequence

This algorithm finds the longest palindrome that is a subsequence of a given input string in $\Theta(n^2)$.

### Example

Input: character
Output: carac

### Code

enum direction { vertical, horizontal, diagonal };

template<typename T>
using matrix = std::vector<std::vector<T>>;

void longest_palindrome_fill_tables(const std::string& input,
matrix<int> &lengths,
matrix<direction> &path) {

int N = input.length();
for (int i = 0; i < N; ++i) {
lengths[i][i] = 1;
}
for (int range = 2; range <= N; ++range) {
for (int i = 0, to = N - range + 1; i < to; ++i) {
int j = i + range - 1;
if (input[i] == input[j]) {
path[i][j] = diagonal;
lengths[i][j] = lengths[i + 1][j - 1] + 2;
}
else if (lengths[i][j - 1] > lengths[i + 1][j]) {
path[i][j] = vertical;
lengths[i][j] = lengths[i][j - 1];
}
else {
path[i][j] = horizontal;
lengths[i][j] = lengths[i + 1][j];
}
}
}
}

void generate_palindrome(int i, int j ,
const matrix<direction>& paths,
const std::string &input,
std::deque<char> &palindrome) {
if (i > j) {
return;
}
if (i == j) {
return palindrome.push_front(input[j]);
}
switch (paths[i][j]) {
case diagonal:
generate_palindrome(i + 1, j - 1, paths, input, palindrome);
palindrome.push_back(input[j]);
return palindrome.push_front(input[j]);
case vertical:
return generate_palindrome(i, j - 1, paths, input, palindrome);
case horizontal:
generate_palindrome(i + 1, j, paths, input, palindrome);
}
}

std::string longest_palindrome(const std::string& input) {
int N = input.length();
matrix<int> lengths(N, std::vector<int>(N, 0));
matrix<direction> paths(N, std::vector<direction>(N, diagonal));

std::deque<char> palindrome;
longest_palindrome_fill_tables(input, lengths, paths);
generate_palindrome(0, N - 1, paths, input, palindrome);
return std::string(palindrome.begin(), palindrome.end());
}