1.简介

　　 字符串匹配就是看看那字符串b是不是字符串a的子串.常用的Knuth-Morris-Pratt 算法，又称KMP算法.

 

2.主要思想

　　当patter在某一位置与string匹配失败时，我们除了知道从string的这个位置进行匹配失败这个结果外，是否可以从前面的匹配中获得更多的信息呢。即当前匹配点匹配失败之后,向右滑动的距离是可以提前计算出来的.

 

3.举例

　　

abcabcabcdef   --------- string

　　abcabcdef         --------- pattern

　　KMP就是利用已经匹配了的字符串这个信息，来进行尽可能的向右滑动，避免无谓的比较。匹配字符就是两个字符串的公共部分那么究竟当不匹配的时候，可以向右滑动多远呢？

　　以上面的pattern "abcabcdef"为例：

　　　　当第一个字符不匹配的时候，没有额外信息，那么就向右滑动1个字符。

　　　　当第二个字符不匹配的时候，说明之前匹配的字符为a，但是我们是第二个字符不匹配，还是只能向右滑动1个字符。

　　　　当第三个字符不匹配的时候，说明之前匹配的字符为ab，那么可以向右滑动2位；

　　　　当第四个字符不匹配的时候，说明之前匹配的字符为abc，那么可以向右滑动3位；

　　　　当第五个字符不匹配的时候，说明之前匹配的字符为abca，那么也只能向右滑动3位；

　　　　。。。。。。

 

4.关键问题 

　　那么KMP算法的关键问题就是计算pattern某位置匹配失败的时候，可以向右滑动的位数。

　　下面白话一下如何计算这个滑动位数，0匹配和1匹配时，向右滑动都为1.当匹配数n(n>=2)的时候,在之前匹配的字符串t1中,新增加的字符串t2,且不是t1的23:20:05前端完全重合的字串,则滑动数值加一,否则结束.

 

5.代码

static void Main(string[] args)        {            char[] pattern = { 'a', 'b', 'c', 'a', 'b', 'c', 'd', 'e', 'f' };            int[] table = new int[pattern.Length];            cal_next_table(pattern, table);            Console.Read();        }        static void cal_next_table(char[] pattern,int[] table)        {            //设Table[0]为哨兵            table[0] = 1;            Print(pattern);            Print(table);            for (var i = 1; i < pattern.Length; i++)            {                            table[i] = table[i - 1];                //直接与pattern比较了,以免出现t2长度大于t1的情况                //var t1 = GetSubArr(pattern, 0, i);                //检测t2(注意起点)是否和t1头部重合,重合则break                for(var j=table[i];j

 

6.结果

a b c a b c d e f1 0 0 0 0 0 0 0 0aa b c a b c d e f1 1 0 0 0 0 0 0 0ba ba b c a b c d e f1 1 2 0 0 0 0 0 0ca b ca b c a b c d e f1 1 2 3 0 0 0 0 0aa b c aa b c a b c d e f1 1 2 3 3 0 0 0 0a ba b c a ba b c a b c d e f1 1 2 3 3 3 0 0 0a b ca b c a b ca b c a b c d e f1 1 2 3 3 3 3 0 0a b c db c dc dda b c a b c da b c a b c d e f1 1 2 3 3 3 3 7 0ea b c a b c d ea b c a b c d e f1 1 2 3 3 3 3 7 8

abcabcdef
112333378