Hi,
I was trying to code a problem on printing all possible LIS of a string in sorted order. The link to the problem is http://www.spoj.com/problems/UPSUB/. My idea is simply to calculate a 2D LCS matrix by LCS(string s, sort(string s)) and then backtrack over the LCS matrix with optimization to get all the LIS. I am facing problems in optimizing my backtracking code because its visiting way too many states that required.
#include <bits/stdc++.h>
using namespace std;
/*u,l,d correspond to the possible directions from which the maximum value of the LCS array came from*/
struct node{
int val,u,l,d;
};
int n,maxlen;
set<string> ans;
string s,s1;
//int vis[110][110];
vector<vector<node > > dp;
/*calculates LIS=LCS(s,sort(s))*/
void lis(void){
s1=s;
sort(s1.begin(),s1.end());
//cout<<s1<<endl;
for(int i=1;i<=n;i++){
for(int j=0;j<=n;j++){
if(s1[i-1]==s[j-1]){
/*if(i==1 and j==2)
cout<<"Came wrong way "<<endl;*/
int x=max(max(dp[i-1][j].val,dp[i][j-1].val),dp[i-1][j-1].val+1);
dp[i][j].val=x;
if(dp[i-1][j].val==x){
dp[i][j].u=1;
}
if(dp[i][j-1].val==x){
dp[i][j].l=1;
}
if((dp[i-1][j-1].val+1)==x){
dp[i][j].d=1;
}
}
else{
int x=max(dp[i-1][j].val,dp[i][j-1].val);
dp[i][j].val=x;
if(dp[i-1][j].val==x){
dp[i][j].u=1;
}
if(dp[i][j-1].val==x){
dp[i][j].l=1;
}
}
}
}
maxlen=dp[n][n].val;
//cout<<maxlen<<endl;
}
string st;
void dfs(int x,int y){
cout<<"now at "<<x<<"\t"<<y<<endl;
if(x==0 or y==0){
if(st.size()==maxlen){
set<string>::iterator it=ans.begin();
ans.insert(it,st);
//cout<<"print at "<<x<<"\t"<<y<<endl;
}
return;
}
if(dp[x][y].d==1 ){
st=s[y-1]+st;
dfs(x-1,y-1);
st.erase(st.begin(),st.begin()+1);
}
if(dp[x][y].u==1){
dfs(x-1,y);
}
if(dp[x][y].l==1){
dfs(x,y-1);
}
}
void print_lis(void){
for(int i=0;i<=n;i++){
cout<<endl;
for(int j=0;j<=n;j++){
cout<<dp[i][j].val<<"\t";
}
}
cout<<endl;
}
int main(void){
int tc;
cin>>tc;
while(tc--){
cin>>s;
n=s.size();
dp.resize(n+1);
for(int i=0;i<=n;i++){
dp[i].resize(n+1);
}
lis();
//print_lis();
dfs(n,n);
//sort(ans.begin(),ans.end());
for(set<string>::iterator it=ans.begin();it!=ans.end();it++)
cout<<*it<<endl;
}
return 0;
}
Please suggest me some ways by which I can optimize the dfs(i,j) part.
