求最长公共子序列的子序列 dfs+dp

朋友分享的一道面试题

要求删除掉任意长度的字符串s1之后，获得的最长的回文串都有哪些？
因为回文串的性质，反转后不变，那么可以将字符串s1反转成s2。
如果存在一个最长的回文串，那么肯定是s1和s2的最长公共子序列。
通常我们会求出最长公共子序列的长度alen，这次要把所有的子序列输出来。

可以通过观察dp矩阵，发现这样一个规律（图忘记从哪里盗来的了）

可以通过标有圆圈的点，找到所有的子串，标有圆圈的点，可以通过s1[i]==s2[j]找到，然后可以放在一个二维数组里。

然后进一步通过dfs，去找下一个标有圆圈的点,如果找到的长度为alen了，说明这就是一个答案，因为是通过遍历所有可能解，所以可能存在重复值，可以用set去重。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <set>
using namespace std;
const int maxn = 1005;
int len;        //当前长度 
int alen;        //总长度 
int ans;        
int top;
int top2;
int dp[maxn][maxn];
int arr[2][maxn];
char stc[maxn];
string s1,s2;
set<string> col;

string reverseStr(string s1){    //字符串反转 
    string s2 = s1;
    reverse(s2.begin(),s2.end());
    return s2;
}
void init(){                    //dp矩阵初始化 
    for(int i=0;i<maxn;++i){
        for(int j=0;j<maxn;++j){
            dp[i][j]=0;
        }
    }
}
void printMap(int len1,int len2){        //打印dp 
    for(int i=1;i<=len1;++i){
        for(int j=1;j<=len2;++j){
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }
}

void dfs(int x,int y,int pos){            //dfs搜索符合总长度的子串 
    if(top2==alen){
        stc[top2]='\0';
        //cout<<stc<<endl;
        col.insert(stc);
    }
    for(int i=pos+1;i<top;++i){
        if(arr[0][i]>arr[0][pos] && arr[1][i]>arr[1][pos]){
            stc[top2++] = s1[arr[0][i]-1];        
            dfs(arr[0][i],arr[1][i],i);
            top2--;    
        }
    }
}

int main(){
    //string s1,s2;
    while(cin>>s1){
        //memset(dp,0,sizeof(dp));
        init();
        s2=reverseStr(s1);
        //cout<<s2<<endl;
        int len1 = s1.length();
        int len2 = s2.length();
        //map(len1,len2);
        //dp求出最长子序列长度 
        int i , j ;
        for( i = 1; i <= len1;++i){
            for( j = 1 ; j <= len2;++j){
                if(s1[i-1] == s2[j-1]){
                    dp[i][j] =  dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                } 
            }
        }
        alen=dp[len1][len2]; 
        //printMap(len1,len2);
        //cout<<dp[len1][len2]<<endl;
        top=0;

        for(int i=0;i<len1;++i){
            for(int j=0;j<len2;++j){
                if(s1[i]==s2[j]) { 
                    arr[0][top] = i+1;
                    arr[1][top++] = j+1;
                }
            }
        }
        
        col.clear();    
        for(int i=0;i<top;++i){
            stc[top2++]=s1[arr[0][i]-1];
            dfs(arr[0][i],arr[1][i],i);
            top2--;
        }
        set<string>::iterator iter;
        //cout<<col.size()<<" !!!"<<endl;
        for(iter=col.begin();iter!=col.end();++iter){
            cout<<*iter<<endl;
        }
    }
    return 0;
}