1
\$\begingroup\$

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());
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.