字符串对比算法源代码(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;
}

此条目发表在C++分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论