字符串对比算法源代码(C++版)

admin1

[code]注意:需要在

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;
}[/code]