lcslengthview.cpp

该程序为算法分析中的一个经典问题

// LCSLENGTHView.cpp : implementation of the CLCSLENGTHView class
//

#include "stdafx.h"
#include "LCSLENGTH.h"

#include "LCSLENGTHDoc.h"
#include "LCSLENGTHView.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CLCSLENGTHView

IMPLEMENT_DYNCREATE(CLCSLENGTHView, CFormView)

BEGIN_MESSAGE_MAP(CLCSLENGTHView, CFormView)
	//{{AFX_MSG_MAP(CLCSLENGTHView)
	ON_BN_CLICKED(IDC_BUTTON1, OnButton1)
	//}}AFX_MSG_MAP
	// Standard printing commands
	ON_COMMAND(ID_FILE_PRINT, CFormView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CFormView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CFormView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CLCSLENGTHView construction/destruction

CLCSLENGTHView::CLCSLENGTHView()
	: CFormView(CLCSLENGTHView::IDD)
{
	//{{AFX_DATA_INIT(CLCSLENGTHView)
		// NOTE: the ClassWizard will add member initialization here
	//}}AFX_DATA_INIT
	// TODO: add construction code here

}

CLCSLENGTHView::~CLCSLENGTHView()
{
}

void CLCSLENGTHView::DoDataExchange(CDataExchange* pDX)
{
	CFormView::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CLCSLENGTHView)
		// NOTE: the ClassWizard will add DDX and DDV calls here
	//}}AFX_DATA_MAP
}

BOOL CLCSLENGTHView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	return CFormView::PreCreateWindow(cs);
}

void CLCSLENGTHView::OnInitialUpdate()
{
	CFormView::OnInitialUpdate();
	GetParentFrame()->RecalcLayout();
	ResizeParentToFit();

}

/////////////////////////////////////////////////////////////////////////////
// CLCSLENGTHView printing

BOOL CLCSLENGTHView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// default preparation
	return DoPreparePrinting(pInfo);
}

void CLCSLENGTHView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add extra initialization before printing
}

void CLCSLENGTHView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add cleanup after printing
}

void CLCSLENGTHView::OnPrint(CDC* pDC, CPrintInfo* /*pInfo*/)
{
	// TODO: add customized printing code here
}

/////////////////////////////////////////////////////////////////////////////
// CLCSLENGTHView diagnostics

#ifdef _DEBUG
void CLCSLENGTHView::AssertValid() const
{
	CFormView::AssertValid();
}

void CLCSLENGTHView::Dump(CDumpContext& dc) const
{
	CFormView::Dump(dc);
}

CLCSLENGTHDoc* CLCSLENGTHView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CLCSLENGTHDoc)));
	return (CLCSLENGTHDoc*)m_pDocument;
}
#endif //_DEBUG

int CLCSLENGTHView::ConstructSubString(char * x,int * b[],char * ss,int i,int j)
{
    int k;

    if (i==0 || j==0) return 0;
    if (b[i][j]==1)
    {
	ConstructSubString(x,b,ss,i-1,j-1);
	k=strlen(ss);
	ss[k]=x[i-1];
	ss[k+1]=0;
    }
    else
    if (b[i][j]==2)
	ConstructSubString(x,b,ss,i-1,j);
    else
	ConstructSubString(x,b,ss,i,j-1);
    return 0;
}

int CLCSLENGTHView::LcsLength(char * x,char * y)
{
    int * c[4096];
    int * b[4096];
    int   i,j,m,n;
    int * z;
    char ss[4096];

    m=strlen(x);				// 求 x 的串长
    n=strlen(y);				// 求 y 的串长

    z=(int *)malloc(2*(m+2)*(n+2)*sizeof(int));	// 分配空间
    for (i=0;i<=m;i++)
    {
	c[i]=z;
	z=&z[n+1];
    }
    for (i=0;i<=m;i++)
    {
	b[i]=z;
	z=&z[n+1];
    }

    for (i=0;i<=m;i++) c[i][0]=0;
    for (i=0;i<=n;i++) c[0][i]=0;

    for (i=1;i<=m;i++)
    for (j=1;j<=n;j++)
    if (x[i-1]==y[j-1])
    {
	c[i][j]=c[i-1][j-1]+1;
	b[i][j]=1;
    }
    else
    if (c[i-1][j]>c[i][j-1])
    {
	c[i][j]=c[i-1][j];
	b[i][j]=2;
    }
    else
    {
	c[i][j]=c[i][j-1];
	b[i][j]=3;
    }
    ss[0]=0;
    ConstructSubString(x,b,ss,m,n);
    SetDlgItemText(IDC_EDIT3,ss);
    free(c[0]);
    return 0;
}

/////////////////////////////////////////////////////////////////////////////
// CLCSLENGTHView message handlers

void CLCSLENGTHView::OnButton1() 
{
	// TODO: Add your control notification handler code here
	char ss1[1024];
	char ss2[1024];

	GetDlgItemText(IDC_EDIT1,ss1,sizeof(ss1));
	GetDlgItemText(IDC_EDIT2,ss2,sizeof(ss2));
	LcsLength(ss1,ss2);
}