#include "StdAfx.h"
#include "AlgorithmLCS.h"
template <class T>
AlgorithmLCS<T>::AlgorithmLCS(void)
{
reset();
}
template <typename T>
void AlgorithmLCS<T>::setSeq(SeqBM seqBM,T * seq,int len)
{
vector<T> & vSeq=(seqBM==SEQ_A)?seqA:seqB;
vSeq.clear();vSeq.push_back(seq[0]);//0下标元素是不使用的
for(int i=0;i<len;i++)
{
vSeq.push_back(seq[i]);
}
if(seqBM==SEQ_A)
{
lenA=vSeq.size()-1;
}
else
{
lenB=vSeq.size()-1;
}
}
template <typename T>
void AlgorithmLCS<T>::reset()
{
memset(Lcs,0,sizeof(T)*MAX_LENGTH*MAX_LENGTH);
memset(Dir,0,sizeof(Dir[0][0])*MAX_LENGTH*MAX_LENGTH);
seqA.clear();
seqB.clear();
vLcs.clear();
lcsStack.clear();
}
template <typename T>
void AlgorithmLCS<T>::solve()
{
for(int i=1;i<=lenA;i++)
{
for(int j=1;j<=lenB;j++)
{
if(seqA[i]==seqB[j])
{
Lcs[i][j]=Lcs[i-1][j-1]+1;
Dir[i][j]=SLASH;//LCS衍生方向为斜向
}
else
{
if(Lcs[i-1][j]<Lcs[i][j-1])
{
Lcs[i][j]=Lcs[i][j-1];
Dir[i][j]=HORIZONTAL;//LCS衍生方向为横向
}
else if(Lcs[i-1][j]>Lcs[i][j-1])
{
Lcs[i][j]=Lcs[i-1][j];
Dir[i][j]=VERTICAL;//LCS衍生方向为纵向
}
else
{
Lcs[i][j]=Lcs[i-1][j];
Dir[i][j]=VERTICAL_HORIZONTAL;//LCS衍生方向为横向和纵向皆有
}
}
}
}
lenLcsOfAB=Lcs[lenA][lenB];//记录下Lcs的长度
}
template <typename T>
void AlgorithmLCS<T>::DFS(int row,int col)
{
//printf("走到(%d,%d)\n",row,col);
if(Lcs[row][col]==lenLcsOfAB)//搜索到路径了
{
vLcs.push_back(lcsStack);
}
else
{
if(Dir[row+1][col+1]==SLASH)
{
lcsStack.push_back(seqA[row+1]);
DFS(row+1,col+1);
lcsStack.pop_back();
}
if(Dir[row][col+1]==HORIZONTAL||Dir[row][col+1]==VERTICAL_HORIZONTAL)
{
DFS(row,col+1);
}
if(Dir[row+1][col]==VERTICAL||Dir[row+1][col]==VERTICAL_HORIZONTAL)
{
DFS(row+1,col);
}
}
}
template <typename T>
void AlgorithmLCS<T>::calculateALLLcs()
{
if(lenLcsOfAB)//如果没有Lcs那么就不必计算了
{
lcsStack.clear();
for(int i=0;i<=lenA;i++)
{
if(Dir[i+1][1]==SLASH)
{
lcsStack.push_back(seqB[1]);
DFS(i+1,1);
lcsStack.pop_back();
}
if(Dir[i][1]==HORIZONTAL||Dir[i][1]==VERTICAL_HORIZONTAL)
{
DFS(i,1);
}
}
for(int j=1;j<=lenB;j++)
{
if(Dir[1][j+1]==SLASH)
{
lcsStack.push_back(seqA[1]);
DFS(1,j+1);
lcsStack.pop_back();
}
if(Dir[1][j]==VERTICAL||Dir[1][j]==VERTICAL_HORIZONTAL)
{
DFS(1,j);
}
}
}
}
template <typename T>
int AlgorithmLCS<T>::getLenOfLcs()
{
return lenLcsOfAB;
}
template <typename T>
const vector<vector<T>>& AlgorithmLCS<T>::getAllLcs()
{
return vLcs;
}
template <typename T>
void AlgorithmLCS<T>::printMatrixLcs()
{
for(int i=0;i<=lenA;i++)
{
for(int j=0;j<=lenB;j++)
{
cout<<Lcs[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
}
template <typename T>
void AlgorithmLCS<T>::printMatrixDirection()
{
for(int i=0;i<=lenA;i++)
{
for(int j=0;j<=lenB;j++)
{
cout<<Dir[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
}
template <typename T>
AlgorithmLCS<T>::~AlgorithmLCS(void)
{
}