From boitboy on 2013-12-13 22:33:31
字符串对比算法源代码(C++版)
注意:需要在
BOOL CTextCompareCppApp::InitInstance()
加上
AfxInitRichEdit2();
否则CRichEditCtrl 无法使用
// TextCompareCppDlg.h : 头文件
//
#pragma once
// CTextCompareCppDlg 对话框
class CTextCompareCppDlg : public CDialog
{
// 构造
public:
CTextCompareCppDlg(CWnd* pParent = NULL); // 标准构造函数
// 对话框数据
enum { IDD = IDD_TEXTCOMPARECPP_DIALOG };
protected:
virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV 支持
// 实现
protected:
HICON m_hIcon;
// 生成的消息映射函数
virtual BOOL OnInitDialog();
afx_msg void OnSysCommand(UINT nID, LPARAM lParam);
afx_msg void OnPaint();
afx_msg HCURSOR OnQueryDragIcon();
void ChangeColor(int leftStart, int leftEnd, int rightStart, int rightEnd,bool bSame);
CRichEditCtrl richTextBox1;
CRichEditCtrl richTextBox2;
DECLARE_MESSAGE_MAP()
public:
afx_msg void OnBnClickedButton1();
};
// TextCompareCppDlg.cpp : 实现文件
//
#include "stdafx.h"
#include "TextCompareCpp.h"
#include "TextCompareCppDlg.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#endif
struct IndexPair
{
int l;
int r;
IndexPair()
{
l=0;
r=0;
}
};
COLORREF ColorNew = RGB(253,0,0);
COLORREF ColorDelete =RGB(254,0,0);
COLORREF ColorModify = RGB(255,0,0);
COLORREF ColorSame = RGB(0,0,0);//黑色
// 用于应用程序“关于”菜单项的 CAboutDlg 对话框
class CAboutDlg : public CDialog
{
public:
CAboutDlg();
// 对话框数据
enum { IDD = IDD_ABOUTBOX };
protected:
virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV 支持
// 实现
protected:
DECLARE_MESSAGE_MAP()
};
CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
}
void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
}
BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
END_MESSAGE_MAP()
// CTextCompareCppDlg 对话框
CTextCompareCppDlg::CTextCompareCppDlg(CWnd* pParent /*=NULL*/)
: CDialog(CTextCompareCppDlg::IDD, pParent)
{
m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}
void CTextCompareCppDlg::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
DDX_Control(pDX,IDC_RICHEDIT21,richTextBox1);
DDX_Control(pDX,IDC_RICHEDIT22,richTextBox2);
}
BEGIN_MESSAGE_MAP(CTextCompareCppDlg, CDialog)
ON_WM_SYSCOMMAND()
ON_WM_PAINT()
ON_WM_QUERYDRAGICON()
//}}AFX_MSG_MAP
ON_BN_CLICKED(IDC_BUTTON1, &CTextCompareCppDlg::OnBnClickedButton1)
END_MESSAGE_MAP()
// CTextCompareCppDlg 消息处理程序
BOOL CTextCompareCppDlg::OnInitDialog()
{
CDialog::OnInitDialog();
// 将“关于...”菜单项添加到系统菜单中。
// IDM_ABOUTBOX 必须在系统命令范围内。
ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
ASSERT(IDM_ABOUTBOX < 0xF000);
CMenu* pSysMenu = GetSystemMenu(FALSE);
if (pSysMenu != NULL)
{
CString strAboutMenu;
strAboutMenu.LoadString(IDS_ABOUTBOX);
if (!strAboutMenu.IsEmpty())
{
pSysMenu->AppendMenu(MF_SEPARATOR);
pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
}
}
// 设置此对话框的图标。当应用程序主窗口不是对话框时，框架将自动
// 执行此操作
SetIcon(m_hIcon, TRUE); // 设置大图标
SetIcon(m_hIcon, FALSE); // 设置小图标
// TODO: 在此添加额外的初始化代码
SetDlgItemText(IDC_EDIT1,_T("CAD工具之家(
www.cadgj.com)XX"));
SetDlgItemText(IDC_EDIT2,_T("CAD工具(cbd_gj.com)"));
return TRUE; // 除非将焦点设置到控件，否则返回 TRUE
}
void CTextCompareCppDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
if ((nID & 0xFFF0) == IDM_ABOUTBOX)
{
CAboutDlg dlgAbout;
dlgAbout.DoModal();
}
else
{
CDialog::OnSysCommand(nID, lParam);
}
}
// 如果向对话框添加最小化按钮，则需要下面的代码
// 来绘制该图标。对于使用文档/视图模型的 MFC 应用程序，
// 这将由框架自动完成。
void CTextCompareCppDlg::OnPaint()
{
if (IsIconic())
{
CPaintDC dc(this); // 用于绘制的设备上下文
SendMessage(WM_ICONERASEBKGND, reinterpret_cast<WPARAM>(dc.GetSafeHdc()), 0);
// 使图标在工作矩形中居中
int cxIcon = GetSystemMetrics(SM_CXICON);
int cyIcon = GetSystemMetrics(SM_CYICON);
CRect rect;
GetClientRect(&rect);
int x = (rect.Width() - cxIcon + 1) / 2;
int y = (rect.Height() - cyIcon + 1) / 2;
// 绘制图标
dc.DrawIcon(x, y, m_hIcon);
}
else
{
CDialog::OnPaint();
}
}
//当用户拖动最小化窗口时系统调用此函数取得光标显示。
//
HCURSOR CTextCompareCppDlg::OnQueryDragIcon()
{
return static_cast<HCURSOR>(m_hIcon);
}
void RichEditCtrlSelect(CRichEditCtrl* pCtrl,int start, int length)
{
if(length-1<0)
{
return;
}
pCtrl->SetSel(start,start+length);
}
void RichEditCtrlChangeTextColor(CRichEditCtrl* pCtrl,COLORREF& col)
{
if(col==ColorDelete)
{
CHARFORMAT2 cf;
pCtrl->GetSelectionCharFormat(cf);
cf.crTextColor=col;
cf.dwEffects&=~CFE_AUTOCOLOR;
cf.dwMask|=CFM_COLOR;
cf.dwEffects|=CFE_STRIKEOUT;
pCtrl->SetSelectionCharFormat(cf);
}
else if(col==ColorModify)
{
CHARFORMAT2 cf;
pCtrl->GetSelectionCharFormat(cf);
cf.crTextColor=col;
cf.dwEffects&=~CFE_AUTOCOLOR;
cf.dwMask|=CFM_COLOR;
cf.dwEffects&=~CFE_STRIKEOUT;
pCtrl->SetSelectionCharFormat(cf);
}
else if(col==ColorNew)
{
CHARFORMAT2 cf;
pCtrl->GetSelectionCharFormat(cf);
cf.crTextColor=RGB(0,0,255);
cf.dwEffects&=~CFE_AUTOCOLOR;
cf.dwMask|=CFM_COLOR;
cf.dwEffects&=~CFE_STRIKEOUT;
pCtrl->SetSelectionCharFormat(cf);
}
else if(col==ColorSame)
{
CHARFORMAT2 cf;
pCtrl->GetSelectionCharFormat(cf);
cf.crTextColor=RGB(0,0,0);
cf.dwEffects&=~CFE_AUTOCOLOR;
cf.dwMask|=CFM_COLOR;
cf.dwEffects&=~CFE_STRIKEOUT;
pCtrl->SetSelectionCharFormat(cf);
}
}
void CTextCompareCppDlg::ChangeColor(int leftStart, int leftEnd, int rightStart, int rightEnd,bool bSame)
{
int leftLen = leftEnd - leftStart + 1;
int rightLen = rightEnd - rightStart + 1;
if(leftLen==0&&rightLen==0)
{
return;
}
if (leftLen > rightLen)
{
//删除了内容,长度为(leftLen - rightLen)
RichEditCtrlSelect(&richTextBox1,leftStart, leftLen - rightLen);
RichEditCtrlChangeTextColor(&richTextBox1,ColorDelete);
if (rightLen > 0)
{
//修改了内容,长度为(rightLen)
RichEditCtrlSelect(&richTextBox2,rightStart, rightLen);
RichEditCtrlChangeTextColor(&richTextBox2,bSame ? ColorSame : ColorModify);
RichEditCtrlSelect(&richTextBox1,leftStart + leftLen - rightLen - 1+1, rightLen);
RichEditCtrlChangeTextColor(&richTextBox1,bSame ? ColorSame : ColorModify);
}
}
else if (leftLen == rightLen)
{
//修改了内容,长度为(leftLen)
RichEditCtrlSelect(&richTextBox2,rightStart, rightLen);
RichEditCtrlChangeTextColor(&richTextBox2,bSame ? ColorSame : ColorModify);
RichEditCtrlSelect(&richTextBox1,leftStart, leftLen);
RichEditCtrlChangeTextColor(&richTextBox1,bSame ? ColorSame : ColorModify);
}
else
{
//增加了内容,长度为(rightLen-leftLen)
RichEditCtrlSelect(&richTextBox2,rightStart, rightLen - leftLen);
RichEditCtrlChangeTextColor(&richTextBox2,ColorNew);
if (leftLen > 0)
{
//修改了内容，长度为(leftLen)
RichEditCtrlSelect(&richTextBox1,leftStart, leftLen);
RichEditCtrlChangeTextColor(&richTextBox1,bSame ? ColorSame : ColorModify);
RichEditCtrlSelect(&richTextBox2,rightStart + rightLen - leftLen - 1+1, leftLen);
RichEditCtrlChangeTextColor(&richTextBox2,bSame ? ColorSame : ColorModify);
}
}
}
void CTextCompareCppDlg::OnBnClickedButton1()
{
// TODO: 在此添加控件通知处理程序代码
CString leftText,rightText;
GetDlgItemText(IDC_EDIT1,leftText);
richTextBox1.SetWindowText(leftText);
GetDlgItemText(IDC_EDIT2,rightText);
richTextBox2.SetWindowText(rightText);
WCHAR* left=new WCHAR[leftText.GetLength()+1];
memset(left,0,(leftText.GetLength()+1)*sizeof(WCHAR));
//特别注意，一定要转换为宽字节的，不然对比出错
#ifdef _UNICODE
lstrcpy(left,leftText);
#else
MultiByteToWideChar(CP_ACP, MB_PRECOMPOSED, leftText, leftText.GetLength(), left, leftText.GetLength() + 1);
#endif
WCHAR* right=new WCHAR[rightText.GetLength()+1];
memset(right,0,(rightText.GetLength()+1)*sizeof(WCHAR));
#ifdef _UNICODE
lstrcpy(right,rightText);
#else
MultiByteToWideChar(CP_ACP, MB_PRECOMPOSED, rightText, rightText.GetLength(), right, rightText.GetLength() + 1);
#endif
int leftLen = lstrlenW(left);
int rightLen = lstrlenW(right);
if(leftLen==0&&rightLen==0)
{
//都是空的内容
delete[] left;
delete[] right;
return;
}
else if(leftLen==0&&rightLen>0)
{
//全部都是新增的
RichEditCtrlSelect(&richTextBox2,0, rightLen);
RichEditCtrlChangeTextColor(&richTextBox2,ColorNew);
delete[] left;
delete[] right;
return;
}
else if(leftLen>0&&rightLen==0)
{
//全部都被删除了
RichEditCtrlSelect(&richTextBox1,0, leftLen);
RichEditCtrlChangeTextColor(&richTextBox1,ColorDelete);
delete[] left;
delete[] right;
return;
}
bool** V=new bool*[leftLen];//申请一个动态的二维数组
int l = 0;
int r = 0;
for(l=0;l<leftLen;l++)
{
V[l]=new bool[rightLen];//申请动态一维数组
}
for (l = 0; l < leftLen; l++)
{
WCHAR c1 = left[l];
for (r = 0; r < rightLen; r++)
{
WCHAR c2 = right[r];;
if (c1 == c2)
{
V[l][r] = true;
}
else
{
V[l][r] = false;
}
}
}
int nMax = 0;
int** N = new int*[leftLen];//申请动态二维数组
for(l=0;l<leftLen;l++)
{
N[l]=new int[rightLen];//申请动态一维数组
}
for (l = leftLen - 1; l >= 0; l--)
{
for (r = rightLen - 1; r >= 0; r--)
{
if (l == leftLen - 1 && r == rightLen - 1)
{
if (V[l][r])
{
N[l][r] = 1;
}
else
{
N[l][r] = 0;
}
}
else if (l == leftLen - 1)
{
if (V[l][r])
{
N[l][r] = 1;
}
else
{
N[l][r] = N[l][r+1];
}
}
else if (r == rightLen - 1)
{
if (V[l][r])
{
N[l][r] = 1;
}
else
{
N[l][r] = N[l+1][r];
}
}
else
{
N[l][r] = max(max(N[l+1][r], N[l][r+1]), V[l][r] ? N[l+1][r+1] + 1 : N[l+1][r+1]);
}
if (N[l][r] > nMax)
{
nMax = N[l][r];
}
}
}
if (nMax == 0)
{
//未找到任何匹配
ChangeColor(0, leftLen - 1, 0, rightLen - 1,false);
//释放二维数组V
for(l=0;l<leftLen;l++)
{
delete[] V[l];
}
delete[] V;
//释放二维数组N
for(l=0;l<leftLen;l++)
{
delete[] N[l];
}
delete[] N;
delete[] left;
delete[] right;
return;
}
CArray<IndexPair> pairList;
for (l = leftLen - 1; l >= 0; l--)
{
for (r = rightLen - 1; r >= 0; r--)
{
if (N[l][r] == nMax && V[l][r])
{
//起始点
IndexPair pair;
pair.l = l;
pair.r = r;
pairList.Add(pair);
}
}
}
IndexPair firstIndex;
//寻找最优路径
int nMin = -1;
int** D = new int*[leftLen];//申请动态二维数组
for(l=0;l<leftLen;l++)
{
D[l]=new int[rightLen];//申请动态一维数组
}
for (l = leftLen - 1; l >= 0; l--)
{
for (r = rightLen - 1; r >= 0; r--)
{
if (l == leftLen - 1 && r == rightLen - 1)
{
if (V[l][r])
{
D[l][r] = 1;
}
else
{
D[l][r] = 0;
}
}
else if (l == leftLen - 1)
{
if (V[l][r])
{
D[l][r] = 1;
}
else
{
if (D[l][r + 1] > 0)
{
D[l][r] = D[l][r + 1] + 1;
}
else
{
D[l][r] = 0;
}
}
}
else if (r == rightLen - 1)
{
if (V[l][r])
{
D[l][r] = 1;
}
else
{
D[l][r] = D[l + 1][r];
}
}
else
{
if (V[l][r])
{
D[l][r] = D[l + 1][r + 1] + 1;
}
else
{
if (N[l][r + 1] > N[l + 1][r])
{
D[l][r] = D[l][r + 1] + 1;
}
else
{
D[l][r] = D[l + 1][r];
}
}
}
}
}
for (int i = 0; i < pairList.GetCount(); i++)
{
IndexPair& pair = pairList.GetAt(i);
if (D[pair.l][pair.r] < nMin || nMin < 0)
{
nMin = D[pair.l][pair.r];
firstIndex = pair;
}
}
pairList.RemoveAll();
pairList.Add(firstIndex);
while (true)
{
//寻找下一个合理的点
IndexPair& lastIndex = pairList.GetAt(pairList.GetCount() - 1);
if (lastIndex.l == leftLen - 1 || lastIndex.r == rightLen - 1)
{
//找到边缘了
if (V[lastIndex.l][lastIndex.r])
{
IndexPair newPair;
newPair.l = lastIndex.l;
newPair.r = lastIndex.r;
pairList.Add(newPair);
break;
}
else
{
if (lastIndex.r != rightLen - 1)
{
for (r = lastIndex.r + 1; r <= rightLen - 1; r++)
{
if (V[lastIndex.l][r])
{
IndexPair newPair;
newPair.l = lastIndex.l;
newPair.r = r;
pairList.Add(newPair);
break;
}
}
}
else if (lastIndex.l != leftLen - 1)
{
for (l = lastIndex.l; l <= leftLen - 1; l++)
{
IndexPair newPair;
newPair.l = l;
newPair.r = lastIndex.r;
pairList.Add(newPair);
break;
}
}
break;
}
}
if (V[lastIndex.l][lastIndex.r])
{
IndexPair newPair;
newPair.l = lastIndex.l + 1;
newPair.r = lastIndex.r + 1;
pairList.Add(newPair);
}
else
{
if (N[lastIndex.l][lastIndex.r + 1] > N[lastIndex.l + 1][lastIndex.r])
{
IndexPair newPair;
newPair.l = lastIndex.l;
newPair.r = lastIndex.r + 1;
pairList.Add(newPair);
}
else
{
IndexPair newPair;
newPair.l = lastIndex.l+1;
newPair.r = lastIndex.r;
pairList.Add(newPair);
}
}
}
for (int i = pairList.GetCount() - 1; i >= 0; i--)
{
IndexPair pair = pairList.GetAt(i);
if (!V[pair.l][pair.r])
{
pairList.RemoveAt(i);
}
}
for (int i = pairList.GetCount() - 2; i >= 0; i--)
{
IndexPair& pair1 = pairList.GetAt(i+1);
IndexPair& pair2 = pairList.GetAt(i);
for (int j = pair1.r - 1; j >= pair2.r + 1; j--)
{
if (right[j] == right[pair2.r])
{
pair2.r = j;
pairList.SetAt(i,pair2);
break;
}
}
}
int leftLast = 0;
int rightLast = 0;
IndexPair pair0 = pairList.GetAt(0);
IndexPair pairTmp = pair0;
//left的pair0.l和right的pair0.r匹配
ChangeColor(0, pair0.l - 1, 0, pair0.r - 1, false);
RichEditCtrlSelect(&richTextBox1,pair0.l, 1);
RichEditCtrlChangeTextColor(&richTextBox1,ColorSame);
RichEditCtrlSelect(&richTextBox2,pair0.r, 1);
RichEditCtrlChangeTextColor(&richTextBox2,ColorSame);
for (int i = 1; i < pairList.GetCount(); i++)
{
IndexPair pair1 = pairList.GetAt(i - 1);
IndexPair pair2 = pairList.GetAt(i);
if (pair2.l - pair1.l == 1 &&
pair2.r - pair1.r == 1)
{
}
else
{
ChangeColor(pair1.l + 1, pair2.l - 1, pair1.r + 1, pair2.r - 1, false);
}
RichEditCtrlSelect(&richTextBox1,pair2.l, 1);
RichEditCtrlChangeTextColor(&richTextBox1,ColorSame);
RichEditCtrlSelect(&richTextBox2,pair2.r, 1);
RichEditCtrlChangeTextColor(&richTextBox2,ColorSame);
if (i == pairList.GetCount() - 1)
{
ChangeColor(pair2.l + 1, leftLen - 1, pair2.r + 1, rightLen - 1, false);
}
}
//释放二维数组V
for(l=0;l<leftLen;l++)
{
delete[] V[l];
}
delete[] V;
//释放二维数组N
for(l=0;l<leftLen;l++)
{
delete[] N[l];
}
delete[] N;
//释放二维数组D
for(l=0;l<leftLen;l++)
{
delete[] D[l];
}
delete[] D;
delete[] left;
delete[] right;
}
