#include <string.h>
#include <iostream.h>
#include "LCS_Length.h"
#include <time.h>
#include <stdlib.h>
template<typename T>
void LCS_Length(T x[],T y[]); // 计算LCS的长度，并标记
template<typename T>
void PRINT_LCS(T x[],int i,int j); //构造一个LCS并打印出来
void Rdom(void) ; //随机生成分别含有M个和N个元素的两个序列
double spendtime(clock_t start, clock_t end) ; // LCS计算P次所用的时间
int b[M][N]; //存放标记
char x[M],y[N];
int P; //LCS计算次数
//char x[M]={'0','1','2','3','4','5','6','7','8','9'}; //M=10
//char y[N]={'0','1','2','3','4','5','6','7','8','9'}; //N=10
int main(int argc, char* argv[])
{
clock_t start, end;
double cost;
Rdom(); //随机生成分别含有M个和N个元素的两个序列
cout<<endl;
LCS_Length<char>(x,y); // 计算LCS的长度，并标记
cout<<endl;
cout<<"序列X和序列Y的最长子序列(LCS)为：:"<<endl;
PRINT_LCS<char>(x,M-1,N-1); //构造LCS，并输出
cout<<endl;
//根据不同的M值，调整循环次数，减少运行时间
if(M<50)
P=1000000;
else if(M<=500)
P=100000;
else if(M<=5000)
P=10000;
else if(M<=10000)
P=1000;
else
P=100;
cout<<"所用时间还在计算,请等待...................."<<endl;
cost=spendtime(start, end)/P;
cout<<"所用时间为:"<<cost<<"s"<<endl;
return 0;
}
template<typename T>
void LCS_Length(T x[],T y[]) // 计算LCS的长度，并标记
{
int i,j;
int c[M+1][N+1];
for (i=0;i<=N;i++)
{
c[i][0]=0;
}
for(j=0;j<=N;j++)
{
c[0][j]=0;
}
for (i=1;i<=M;i++)
{
for(j=1;j<=N;j++)
{
if(x[i]==y[j])
{
c[i][j]=c[i-1][j-1]+1;
b[i-1][j-1]=LUP;
}
else if(c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
b[i-1][j-1]=UP;
}
else
{
c[i][j]=c[i][j-1];
b[i-1][j-1]=LEFT;
}
}
}
}
template<typename T>
void PRINT_LCS(T x[],int i,int j) //构造一个LCS
{
if(i==-1 || j==-1)
{
return;
}
if(b[i][j]==LUP)
{
PRINT_LCS(x,i-1,j-1);
cout<<x[i];
cout<<" ";
}
else if(b[i][j]==UP)
{
PRINT_LCS(x,i-1,j);
}
else
{
PRINT_LCS(x,i,j-1);
}
}
void Rdom(void) //随机生成分别含有M个和N个元素的两个序列
{
srand( (unsigned)time(NULL)); //设置基准
cout<<"序列X的"<<M<<"个元素为:"<<endl;
for(int i=0;i<M;i++)
{
x[i]= 92+ rand() %25 ; //序列X
cout<<x[i]<<" ";
if((i+1)%20==0)
cout<<endl;
}
cout<<endl;
cout<<"序列Y的"<<N<<"个元素为:"<<endl;
for(i=0;i<N;i++)
{
y[i]=92+ rand() %25 ; //序列Y
cout<<x[i]<<" ";
if((i+1)%20==0)
cout<<endl;
}
}
double spendtime(clock_t start, clock_t end) // LCS计算P次所用的时间
{
start=clock(); //开始时间
for(int i=1;i<=P;i++) //循环P次
{
LCS_Length<char>(x,y); // 计算LCS的长度，并标记
}
end=clock(); //结束时间
return (end - start) / (CLK_TCK); //CLK_TCK=CLOCKS_PER_SEC=1000
}
LCS.rar （14个子文件） 
最长公共子序列（LCS）算法 源程序 LCS_LENGTH 
LCS_LENGTH.opt 53KB LCS_LENGTH.plg 2KB LCS_LENGTH.dsw 545B LCS_Length_Main.cpp 3KB LCS_LENGTH.ncb 49KB LCS_LENGTH.dsp 4KB Debug LCS_LENGTH.pch 266KB
LCS_LENGTH.exe 204KB LCS_LENGTH.ilk 248KB vc60.idb 49KB LCS_Length_Main.obj 12KB LCS_LENGTH.pdb 537KB vc60.pdb 60KB LCS_Length.h 215B
评论0