Here is my code for the problem TRIP.
#include <iostream>
#include <stdio.h>
#include <list>
#include <algorithm>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
using namespace std;
bool sortfunc(char* l,char* r)
{
int i=0;
while(l[i]==r[i])
{
if(l[i]=='\0')
return false;
i++;
}
return l[i]<r[i];
}
struct DPCell
{
int Value;
bool Left;
bool Up;
bool Diag;
public:
DPCell()
{
Value=0;
Left=false;
Up=false;
}
};
struct Loc
{
int x,y;
stack<char> str;
int length;
public:
Loc(int x,int y)
{
this->x=x;
this->y=y;
length=0;
}
};
class DPClass
{
DPCell DPTable[81][81];
char *str1,*str2;
int l1,l2;
queue<Loc> DFSStack;
vector<char*> StringList;
public:
DPClass(char *str1,char *str2)
{
this->str1=str1;
this->str2=str2;
}
void InitDP(int l1,int l2)
{
this->l1=l1;
this->l2=l2;
for(int i=0;i<=l1;i++)
{
for(int j=0;j<l2;j++)
{
DPTable[i][j].Value=0;
DPTable[i][j].Left=false;
DPTable[i][j].Up=false;
DPTable[i][j].Diag=false;
}
}
StringList.clear();
}
void FindLCS()
{
for(int i=1;i<=l1;i++)
{
for(int j=1;j<=l2;j++)
{
if(str1[i-1]==str2[j-1])
{
DPTable[i][j].Value=DPTable[i-1][j-1].Value+1;
DPTable[i][j].Diag=true;
}
else
{
if(DPTable[i][j-1].Value>DPTable[i-1][j].Value)
{
DPTable[i][j].Value=DPTable[i][j-1].Value;
DPTable[i][j].Left=true;
}
else if(DPTable[i][j-1].Value<DPTable[i-1][j].Value)
{
DPTable[i][j].Value=DPTable[i-1][j].Value;
DPTable[i][j].Up=true;
}
else
{
DPTable[i][j].Value=DPTable[i-1][j].Value;
DPTable[i][j].Left=true;
DPTable[i][j].Up=true;
}
}
}
}
}
void BackTrace2()
{
vector<char> s;
int x=l1,y=l2,Count=0;
BackTraceRecursive(x,y,s,Count);
sort(StringList.begin(),StringList.end(),sortfunc);
}
void BackTraceRecursive(int &x,int &y,vector<char> &str,int &Count)
{
if(Count==DPTable[l1][l2].Value)
{
char* st=new char[DPTable[l1][l2].Value+1];
int i=0;
StringList.push_back(st);
vector<char*>::iterator it=(StringList.end());
it--;
for(vector<char>::reverse_iterator jt=str.rbegin();jt<str.rend();jt++)
{
st[i]=(*jt);
i++;
}
st[i]='\0';
}
else if(DPTable[x][y].Up)
{
x--;
BackTraceRecursive(x,y,str,Count);
x++;
if(DPTable[x][y].Left)
{
y--;
BackTraceRecursive(x,y,str,Count);
y++;
}
}
else if(DPTable[x][y].Up)
{
x--;
BackTraceRecursive(x,y,str,Count);
x++;
}
else if(DPTable[x][y].Left)
{
y--;
BackTraceRecursive(x,y,str,Count);
y++;
}
else if(DPTable[x][y].Diag)
{
str.push_back(str1[x-1]);
x--;
y--;
Count++;
BackTraceRecursive(x,y,str,Count);
x++;
y++;
Count--;
str.erase(str.end()-1);
}
}
void PrintStrings()
{
for(vector<char*>::iterator it=StringList.begin();it!=StringList.end();it++)
{
if(it>StringList.begin())
{
if(strcmp(*it,*(it-1)))
printf("%s\n",*it);
}
else
{
printf("%s\n",*it);
}
}
printf("\n");
}
};
int main()
{
int t;
char str1[81],str2[81];
DPClass MyDP(str1,str2);
scanf("%d",&t);
while(t--)
{
scanf("%s",str1);
scanf("%s",str2);
MyDP.InitDP(strlen(str1),strlen(str2));
MyDP.FindLCS();
//MyDP.Result();
MyDP.BackTrace2();
//:x
//MyDP.Test();
MyDP.PrintStrings();
}
return 0;
}
Can someone provide some tips on how to optimize this code.AFAIK the algorithm should be sufficiently fast.I'm using a recursive DFS for finding out all strings.Then I sort it and avoid printing repeating strings.A gprof analysis for a test case reveals that the main bottleneck is my sort comparator function.
Here's a history of what I've done till now.
1.Started out with really slow iterative DFS.
2.Converted to recursive DFS.Speed increased 10 fold.TLE at this point.
3.Tried using C strings instead of cplusplus.Made the code 2-2.5 times slower!!.
Someone please give me some advice.
