字符串对比算法源代码

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);
                }
            }
        }
    }
}