最长回文子序列

算法导论3rd - 15.2

问题描述

回文：palindrome，是正序和逆序完全相同的非空字符串

一个字符串有许多子序列，可以通过删除某些字符而变成回文字符串，字符串“cabbeaf”，删掉‘c’、'e'、‘f’后剩下的子串“abba”就是回文字符串，也是其中最长的回文子序列。在一个给定的字符串中，找到最长的回文子序列，并且返回这个子序列，这就是最长回文子序列LPS问题。注意和最长回文子串的区别，最长回文子串必须是连续的，这里的最长回文子序列，可以是不连续的。

思路

f(i...j) =
    f(i+1...j-1) + 1,               if s[i]==s[j]
    max(f(i+1...j), f(i...j-1)),    else

程序

// 最长回文子序列

#include <iostream>
#include <string>
#include <string.h>
#include <time.h>
#include <new>

using namespace std;

void solve();
template<typename T>
void print_mat(T** mat, int len1, int len2);


int main(int argc, char** argv) {
    clock_t start, end;
    start = clock();
    solve();
    end = clock();

    cout << "time cost: " << (end-start)*1000./CLOCKS_PER_SEC << " ms\n";


    return 0;
}


void solve() {
    //const char* str = "character";
    //const char* str = "mabcmcba";
    const char* str = "cabbeaf";
    int len = strlen(str);
    char* ret = new char[len + 1]{0};
    int** direct = new int*[len]{0};
    int** length = new int*[len]{0};
    for (int i = 0; i < len; ++i) {
        direct[i] = new int[len]{0};
        length[i] = new int[len];
        for (int j = 0; j < len; ++j) {
            length[i][j] = i==j? 1 : -1;
        }
    }

    for (int diff = 1; diff < len; ++diff) {
        for (int i = 0; i < len - diff; ++i) {
            int j = i + diff;
            if (str[i] == str[j]) {
                length[i][j] = (i <= j-2 ? length[i+1][j-1] : 0) + 2;
                direct[i][j] = 3;       // 3代表左侧和右侧都向内缩进
            } else {
                if (length[i+1][j] < length[i][j-1]) {
                    length[i][j] = length[i][j-1];
                    direct[i][j] = 2;   // 2 代表右侧向内缩进
                } else {
                    length[i][j] = length[i+1][j];
                    direct[i][j] = 1;   // 1 代表左侧向内缩进
                }
            }
        }
    }
    int l = length[0][len-1];

    cout << "direct:\n";
    print_mat(direct, len, len);
    cout << "length:\n";
    print_mat(length, len, len);
    cout << "l: " << l << endl;

    // 获取回文字符串
    int begin = 0, end = len-1, idx = 0;
    while (begin < end) {
        switch(direct[begin][end]) {
            case 3:
                ret[idx] = str[begin];
                ret[l-idx-1] = str[begin];
                ++begin;
                --end;
                ++idx;
                break;
            case 2:
                --end;
                break;
            case 1:
                ++begin;
                break;
        }
    }
    if (begin == end) {
        ret[idx] = str[begin];
    }
    cout << "ret: " << ret << endl;

    for (int i = 0; i < len; ++i) {
        delete[] direct[i];
        delete[] length[i];
    }
    delete[] direct;
    delete[] length;
    delete[] ret;
}

template<typename T>
void print_mat(T** mat, int len1, int len2) {
    for (int i = 0; i < len1; ++i) {
        for (int j = 0; j < len2; ++j) {
            cout << mat[i][j] << "\t";
        }
        cout << endl;
    }
}

测试：

direct:
0	1	1	1	1	1	1
0	0	1	1	1	3	2
0	0	0	3	2	2	2
0	0	0	0	1	1	1
0	0	0	0	0	1	1
0	0	0	0	0	0	1
0	0	0	0	0	0	0
length:
1	1	1	2	2	4	4
-1	1	1	2	2	4	4
-1	-1	1	2	2	2	2
-1	-1	-1	1	1	1	1
-1	-1	-1	-1	1	1	1
-1	-1	-1	-1	-1	1	1
-1	-1	-1	-1	-1	-1	1
l: 4
ret: abba
time cost: 0.141 ms