From boitboy on 2013-12-12 20:48:21
字符串对比算法源代码
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
namespace TextCompare
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
public class IndexPair
{
/// <summary>
/// left字符串索引
/// </summary>
public int l = 0;
/// <summary>
/// right字符串索引
/// </summary>
public int r = 0;
public IndexPair Copy()
{
IndexPair newPair = new IndexPair();
newPair.l = l;
newPair.r = r;
return newPair;
}
};
public class IndexPath
{
public List<IndexPair> pairList = new List<IndexPair>();
}
Color ColorNew = Color.Blue;
Color ColorDelete = Color.Red;
Color ColorModify = Color.Yellow;
Color ColorSame = Color.Green;
/// <summary>
/// 改变颜色
/// </summary>
/// <param name="leftStart"></param>
/// <param name="leftEnd"></param>
/// <param name="rightStart"></param>
/// <param name="rightEnd"></param>
/// <param name="bSame"></param>
private void ChangeColor(int leftStart, int leftEnd, int rightStart, int rightEnd, bool bSame)
{
int leftLen = leftEnd - leftStart + 1;
int rightLen = rightEnd - rightStart + 1;
if (leftLen > rightLen)
{
//删除了内容,长度为(leftLen - rightLen)
richTextBox1.Select(leftStart, leftLen - rightLen);
richTextBox1.SelectionColor = ColorDelete;
if (rightLen > 0)
{
//修改了内容,长度为(rightLen)
richTextBox2.Select(rightStart, rightLen);
richTextBox2.SelectionColor = bSame ? ColorSame : ColorModify;
richTextBox1.Select(leftStart + leftLen - rightLen - 1+1, rightLen);
richTextBox1.SelectionColor = bSame ? ColorSame : ColorModify;
}
}
else if (leftLen == rightLen)
{
//修改了内容,长度为(leftLen)
richTextBox2.Select(rightStart, rightLen);
richTextBox2.SelectionColor = bSame ? ColorSame : ColorModify;
richTextBox1.Select(leftStart, leftLen);
richTextBox1.SelectionColor = bSame ? ColorSame : ColorModify;
}
else
{
//增加了内容,长度为(rightLen-leftLen)
richTextBox2.Select(rightStart, rightLen - leftLen);
richTextBox2.SelectionColor = ColorNew;
if (leftLen > 0)
{
//修改了内容，长度为(leftLen)
richTextBox1.Select(leftStart, leftLen);
richTextBox1.SelectionColor = bSame ? ColorSame : ColorModify;
richTextBox2.Select(rightStart + rightLen - leftLen - 1+1, leftLen);
richTextBox2.SelectionColor = bSame ? ColorSame : ColorModify;
}
}
}
private void button1_Click(object sender, EventArgs e)
{
string left = textBox1.Text;
string right = textBox2.Text;
int leftLen = left.Length;
int rightLen = right.Length;
richTextBox1.SelectionColor = Color.Black;
richTextBox2.SelectionColor = Color.Black;
richTextBox1.Text = left;
richTextBox2.Text = right;
//数据为[left,right]
bool[,] V = new bool[leftLen, rightLen];
int l = 0;
int r = 0;
for (l = 0; l < leftLen; l++)
{
char c1 = left[l];
for (r = 0; r < rightLen; r++)
{
char c2 = right[r];
if (c1 == c2)
{
V[l, r] = true;
}
else
{
V[l, r] = false;
}
}
}
int nMax = 0;
int[,] N = new int[leftLen, 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] = Math.Max(Math.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);
return;
}
List<IndexPair> pairList = new List<IndexPair>();
for (l = leftLen - 1; l >= 0; l--)
{
for (r = rightLen - 1; r >= 0; r--)
{
if (N[l, r] == nMax && V[l, r])
{
//起始点
IndexPair pair = new IndexPair();
pair.l = l;
pair.r = r;
pairList.Add(pair);
}
}
}
IndexPair firstIndex = null;
//寻找最优路径
int nMin = -1;
int[,] D = new int[leftLen, 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.Count; i++)
{
IndexPair pair = pairList[i];
if (D[pair.l, pair.r] < nMin || nMin < 0)
{
nMin = D[pair.l, pair.r];
firstIndex = pair;
}
}
pairList.Clear();
pairList.Add(firstIndex);
while (true)
{
//寻找下一个合理的点
IndexPair lastIndex = pairList[pairList.Count - 1];
if (lastIndex.l == leftLen - 1 || lastIndex.r == rightLen - 1)
{
//找到边缘了
if (V[lastIndex.l, lastIndex.r])
{
IndexPair newPair = new IndexPair();
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 = new IndexPair();
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 = new IndexPair();
newPair.l = l;
newPair.r = lastIndex.r;
pairList.Add(newPair);
break;
}
}
break;
}
}
if (V[lastIndex.l, lastIndex.r])
{
IndexPair newPair = new IndexPair();
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 = new IndexPair();
newPair.l = lastIndex.l;
newPair.r = lastIndex.r + 1;
pairList.Add(newPair);
}
else
{
IndexPair newPair = new IndexPair();
newPair.l = lastIndex.l + 1;
newPair.r = lastIndex.r;
pairList.Add(newPair);
}
}
}
for (int i = pairList.Count - 1; i >= 0; i--)
{
IndexPair pair = pairList[i];
if (!V[pair.l, pair.r])
{
pairList.RemoveAt(i);
}
}
for (int i = pairList.Count - 2; i >= 0; i--)
{
IndexPair pair1 = pairList[i + 1];
IndexPair pair2 = pairList[i];
for (int j = pair1.r - 1; j >= pair2.r + 1; j--)
{
if (right[j] == right[pair2.r])
{
pair2.r = j;
break;
}
}
}
int leftLast = 0;
int rightLast = 0;
IndexPair pair0 = pairList[0];
IndexPair pairTmp = pair0;
//left的pair0.l和right的pair0.r匹配
ChangeColor(0, pair0.l - 1, 0, pair0.r - 1, false);
richTextBox1.Select(pair0.l, 1);
richTextBox1.SelectionColor = ColorSame;
richTextBox2.Select(pair0.r, 1);
richTextBox2.SelectionColor = ColorSame;
for (int i = 1; i < pairList.Count; i++)
{
IndexPair pair1 = pairList[i - 1];
IndexPair pair2 = pairList[i];
if (pair2.l - pair1.l == 1 &&
pair2.r - pair2.r == 1)
{
}
else
{
ChangeColor(pair1.l + 1, pair2.l - 1, pair1.r + 1, pair2.r - 1, false);
}
richTextBox1.Select(pair2.l, 1);
richTextBox1.SelectionColor = ColorSame;
richTextBox2.Select(pair2.r, 1);
richTextBox2.SelectionColor = ColorSame;
if (i == pairList.Count - 1)
{
ChangeColor(pair2.l + 1, leftLen - 1, pair2.r + 1, rightLen - 1, false);
}
}
}
}
}
