彩色打印KMP匹配过程

前言：只是为了加深自己对面试题的领悟力，如果有做的错的，请指出，感激。

术语定义：字符串"abc"和字符串"abcadcabc"，如果我们想要求出字符串"abc"在字符串"abcadcabc"中第一次出现的位置，称"abc"是匹配字符串，称"abcadcabc"是被匹配字符串。

KMP算法的原理，网上有很多文章给出了详细的解释，http://www.ruanyifeng.com/blog/2013/05/Knuth–Morris–Pratt_algorithm.html 这篇是阮一峰从字符串前缀和后缀的角度，给去KMP算法的解释，文章写的很好图文并茂，可以帮助大家理解。

http://www.ics.uci.edu/~eppstein/161/960227.html 这篇文章是从有限自动机的角度去解释，当匹配字符串中某个字符串不匹配时，字符串的比较情况，匹配字符串是"nano"，见下图：

文章还给出了算法的详细解释和C++代码实现，有兴趣，可以学习一下。http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm 这个是维基百科关于KMP算法的解释，其中有一个额外连接可以动态的展示KMP的匹配过程，是一个Applet的程序，见 http://people.cs.pitt.edu/~kirk/cs1501/animations/String.html 。效果见下图

 

效果十分的好，可惜我Java不行，而且人家不开源，也尝试下载他们的.class文件，然后通过反编译获取源代码，可以只能找到部分代码，部分.class文件怎么也找不到，于是我就想仿照这个Applet，写一个类似的C#控制台程序出来。

还好憋出来了，见下图。

 

 

先总结教训和经验，再介绍相关代码。

1我开始设计时，我总是想把每一行抽象出来，因为左边一行是左边是要输出内容的解释或者名字，右边是输出的内容，但是在实际过程中需要考虑左边边距的问题，而且输出的内容之间是存在一定的关联的，反正最后一直没有实现。经验和教训是：不要老想着这么优化那么优化，先写出来再说。

2实现过程中也没有什么难点，主要是：在最后一行匹配的时候，显示Searching Info的时候通过控制好控制台的光标，按照不同的颜色显示已经匹配的字符串。主要通过PrintSeahingInfo(int skip,int matching)这个函数实现。 

        /// <summary>
        /// 每次搜索，都调用该函数，显示已经匹配了哪些字符
        /// </summary>
        /// <param name="skip">需要跳过的位置</param>
        /// <param name="matching">已经匹配的字符，匹配的字符用红色显示</param>
        private void PrintSeahingInfo(int skip,int matching) 

3算法实现的比较不好，基本上控制台每行输出对应一个函数，通过线程Sleep 1秒钟，动态显示匹配过程。

下面是实现代码：

    public class ColorFullKMP 
    {
        char[] pattern;
        char[] seachingString;
        int [] overlap;
        //美观程序界面，与左边的距离
        private readonly int INCREMENT = 5;
        private readonly int INCREMENT_2 = 5*3;
        private readonly int INCREMENT_3 = 5 * 6;  
        //打印标题，程序中红字部分
        private void PrintTitle(string title)
        {
            System.ConsoleColor frontColor = Console.ForegroundColor;
            Console.ForegroundColor = System.ConsoleColor.Red;
            Console.CursorTop = Console.CursorTop + 1;
            Console.CursorLeft = INCREMENT;
            Console.Write(title);
            Console.ForegroundColor = frontColor;
        }
        //打印子pattern和seachingString
        private void PrintString(string strName,char []strValue)
        {
            System.ConsoleColor frontColor = Console.ForegroundColor;
            Console.ForegroundColor = System.ConsoleColor.Blue;
            Console.CursorTop = Console.CursorTop + 1;
            Console.CursorLeft = INCREMENT_2;
            Console.Write(strName);
            Console.CursorLeft = INCREMENT_3;
            for (int i = 0; i < strValue.Length; i++)
            {
                Console.Write(strValue[i]);
                Console.Write(' ');
            }
            Console.ForegroundColor = frontColor;
        }
        //对外提供的接口
        public void Binding(string sstring,string strPattern) 
        {
            seachingString=sstring.ToCharArray();
            pattern = strPattern.ToCharArray();
        }
        public ColorFullKMP() 
        {
            string temp = "huhubhuhuhuhaubu";
            seachingString = temp.ToCharArray();
            temp = "huhuhau";
            pattern = temp.ToCharArray();
        }
        //KMP算法中实现get_next部分，初始化overlap
        private void KmpOverlap()
        {
            overlap=new int [pattern.Length+1];
            overlap[0] = -1;
            for (int i = 0; i < pattern.Length; i++)
            {
                overlap[i + 1] = overlap[i] + 1;
                while (overlap[i + 1] > 0 &&
                    pattern[i] != pattern[overlap[i + 1] - 1])
                    overlap[i + 1] = overlap[overlap[i + 1] - 1] + 1;
            }
        }
        private void PrintAlgorithmInfo() 
        {
            PrintTitle("Algorithm Information:");
            PrintIndex();
            PrintString("Pattern:",pattern);
            PrintJump();
        }
        private void PrintIndex() 
        {
            System.ConsoleColor frontColor = Console.ForegroundColor;
            Console.ForegroundColor = System.ConsoleColor.Blue;
            Console.CursorTop = Console.CursorTop + 1;
            Console.CursorLeft = INCREMENT_2;
            Console.Write("Index:");
            Console.CursorLeft = INCREMENT_3;
            for (int i = 0; i < pattern.Length; i++) 
            {
                Console.Write(i);
                Console.Write(' ');
            }
                Console.ForegroundColor = frontColor;
        }
        private void PrintJump() 
        {
            System.ConsoleColor frontColor = Console.ForegroundColor;
            Console.ForegroundColor = System.ConsoleColor.Blue;
            Console.CursorTop = Console.CursorTop + 1;
            Console.CursorLeft = INCREMENT_2;
            Console.Write("Jump Info:");
            Console.CursorLeft = INCREMENT_3-1;
            for (int i = 0; i < overlap.Length-1; i++)
            {
                Console.Write(overlap[i]);
                Console.Write(' ');
            }
            Console.ForegroundColor = frontColor;
        }
        private void PrintSeahingInfo() 
        {
            System.ConsoleColor frontColor = Console.ForegroundColor;
            Console.ForegroundColor = System.ConsoleColor.Blue;
            Console.CursorTop = Console.CursorTop + 1;
            Console.CursorLeft = INCREMENT_2;
            Console.Write("Seahing Info:");
            Console.ForegroundColor = frontColor;
            Console.CursorLeft = INCREMENT_3;
        }
        /*
         * 每次搜索，都调用该函数，显示已经匹配了哪些字符
         */
        /// <summary>
        /// 每次搜索，都调用该函数，显示已经匹配了哪些字符
        /// </summary>
        /// <param name="skip">需要跳过的位置</param>
        /// <param name="matching">已经匹配的字符，匹配的字符用红色显示</param>
        private void PrintSeahingInfo(int skip,int matching) 
        {
            while (Console.CursorLeft > INCREMENT_3)
            {
                Console.CursorLeft--;
                Console.Write(' ');
                Console.CursorLeft--;
            }
            Console.CursorLeft=Console.CursorLeft+skip*2;
            System.ConsoleColor frontColor = Console.ForegroundColor;
            Console.ForegroundColor = System.ConsoleColor.Red;
            int i;
            for (i = 0; i <matching&&i<pattern.Length; i++)
            {
                Console.Write(pattern[i]);
                Console.Write(' ');
            }
            Console.ForegroundColor = System.ConsoleColor.Blue;
            for (; i < pattern.Length; i++) 
            {
                Console.Write(pattern[i]);
                Console.Write(' ');
            }
            Console.ForegroundColor = frontColor;
            Thread.Sleep(1000);
        }
        /*
         对外提供接口，显示KMP过程
         */
        public void PerformSearching() 
        {
            KmpOverlap();
            PrintAlgorithmInfo();
            PrintTitle("Result Information:");
            PrintString("String:", seachingString);
            PrintSeahingInfo();
            int index=IndexOfKMP();
            PrintReport(index);
            Console.ReadKey();
        }
        private void PrintReport(int index)
        {
            System.ConsoleColor frontColor = Console.ForegroundColor;
            Console.ForegroundColor = System.ConsoleColor.Yellow;
            Console.CursorTop = Console.CursorTop + 1;
            Console.CursorLeft = INCREMENT_2;
            if (index < 0)
                Console.Write("Pattern NOT found in the string !");
            else
                Console.Write("Pattern found in the string at postion {0} !",index);
            Console.ForegroundColor = frontColor;
        }
        //实现索引，通过PrintSeahingInfo(int skip,int matching)报告最新匹配情况
        private int IndexOfKMP()
        {
            int index = -1; 
            int i, j;
            i = j = 0;
            PrintSeahingInfo(0,0);
            while (i <=seachingString.Length+j-pattern.Length)
            {
                while (j >= 0 && seachingString[i] != pattern[j])
                {
                    j = overlap[j];
                    if (j >=0)
                        PrintSeahingInfo(i - j, j);
                }
                i++;
                j++;
                PrintSeahingInfo(i - j, j);
                if (j == pattern.Length)
                {
                    index = i - pattern.Length;
                    break;
                }
            }
            return index;
        }
    }

代码的注释比较详细，不用解释了。ColorFullKMP提供了一个binging函数，用来接收匹配字符串和被匹配字符串。在构造函数中初始化了匹配字符串和被匹配字符串，用来直接显示KMP匹配过程。

        static void Main(string[] args)
        {
            ColorFullKMP myCoolKMP = new ColorFullKMP();
            myCoolKMP.PerformSearching();
        }