KMP算法是有三位前辈提出来的一个模式匹配算法，也就是从一个字符串中查找子串的算法，类似C#里面 indexOf （）函数的功能。

如果利用普通的匹配算法去查找子串，最坏的情况下算法复杂度是O((n-m+1)*m) n代表的主串的长度，m代表的是子串的长度，很显然这个算法比较低效。

所以就有大神们发明了KMP算法，它的原理是比普通的匹配算法节省了比对步骤，如主串m=”abcababca”,子串s=”abcabx”，前5个字符是相同的第6个字符不等，那么可以判断子串s中的第一个字符和主串中的第二个，第三个字符也不相等。KMP算法正是省略这些可以判断步骤达到优化匹配算法的目的。

代码如下：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace KMP
{
    class Program
    {
        //计算出子串返回的next数组，当子串不匹配时根据next数组值进行回溯
        static void GetNext(string p, int []next){
            int len = p.Length;
            int i = 0;
            int j = -1;
            next[0] = -1;
            while (i < len)
            {
                if (j == -1 || p[i] == p[j]){
                    ++j;
                    ++i;
                    next[i] = next[j];
                }
                else{
                    j = next[j];//若字符不相同，则j值回溯
                }
            }
        }

        static int Main(string[] args)
        {
            string str = "abccc aabb";
            string sub = "abb";
            int []next = new int[100];
            //计算出子串返回的next数组
            GetNext(sub, next);
            int i = 0;
            int j = 0;
            while (i < str.Length && j < sub.Length) {
                if (j == -1 || str[i] == sub[j] )
                {
                    ++i;
                    ++j;
                }
                else
                    j = next[j];//j回溯到合适的位置
            }
            if (j == sub.Length)
            {
                Console.WriteLine(i - j);
                Console.ReadKey();
                return i - j;
            }
            return 0;
        }
    }
}
  

KMP算法的优化：

后来有人发现上面的KMP算法还是有缺陷的，比如主串m=”aaaabcde” ，子串s=”aaaaax”,由于子串的前面4个字符和主串都是相等的，那么可以用首位next[1]的值去取代与它相等的字符后续的next[j]的值，因此可以对获取next数组的函数进行改良。

static void GetNext(string p, int []next){
            int len = p.Length;
            int i = 0;
            int j = -1;
            next[0] = -1;
            while (i < len)
            {
                if (j == -1 || p[i] == p[j]){
                    j++;
                    i++;
                    if (i < len && p[i] != p[j])
                        next[i] = j;
                    else
                        next[i] = next[j];//改良部分
                }
                else{
                    j = next[j];
                }
            }
        }