KPM算法初步理解

　　一个字符串“FBCABCDABABCDABCDABYW”中是否包含另外一个字符串“ABCDABY”？

　　上面这道题目是一个经典的字符串匹配的题目，对于字符串匹配，比较好的算法里很容易想到KPM算法，那KPM算法是干什么的？为什么说KPM比较优秀？

    给定一个字符串O和F，长度分别是m、n，判断F是否在O中出现，如果出现则返回出现的位置。常规方法是遍历O的每一个字符，与F的每一个字符进行比较，但是这种方法的时间复杂度是T（m*n）,但是KPM算法使得时间复杂度为T（m+n），谁优谁劣就不言而喻了。

    关于其比较思想，我通过图解来说明下：

　（1）字符串”FBCABCDABABCDABCDABYW”的字符和”ABCDABY”的字符进行比较，如果不同就将”ABCDABY”往后移动一位，直到出现和”ABCDABY”首字符匹配的字符。

FBC ABCDAB ABCDABCDABYW

ABCDABY

FBC ABCDAB  ABCDABCDABYW

  　ABCDABY

..........

FBC ABCDAB ABCDABCDABYW

        ABCDABY

（2）哎呦，上面找到第字符相同的了，那接着顺序比较”ABCDABY”中下一个字符，直到出现和”FBCABCDABABCDABCDABYW”中不匹配的字符。

FBC ABCDAB ABCDABCDABYW

        ABCDABY

............

FBC ABCDAB  ABCDABCDABYW

        ABCDABY

（3）妈呀，又出现不匹配了，这时常规想法是将”ABCDABY”整体往后移动一位，然后在逐个比较，这样虽然也行，但是效率比较低，因为前面相同的字符串已经比较过了，再次比较是重复的东西。       

    KPM算法是此时移动位数 = 已经比较的字符数 - 除去最后一个不匹配字符中对应的部分匹配数，这个部分匹配是指F中已经比较的字符串”ABCDAB”中部分O中已经比较的“ABCDAB”重复的最大长度。那F中已经比较的”ABCDAB”字符数是6，O中和”ABCDAB”和F中”ABCDAB”部分重复的字符数是2（”AB”），那6-2=4，关于部分匹配解释如下：

　　部分匹配数组的生成方法如下：

　　先说两个名词：前缀和后缀。

　　前缀：除去最后一个字符，一个字符串的全部组合。

　　后缀：除去第一字符，一个字符串的全部组合。

　　如“ABCDEABC”：

A的前缀后缀都是空，所以临时匹配是0；

AB的前缀是A,后缀是B，临时匹配是0；

ABC的前缀是A、AB，后缀是BC、B，其临时匹配是0；

ABCD的前缀是A、AB、ABC，后缀是BCD、CD、B，其临时匹配是0；

ABCDE前缀是A、AB、ABC、ABCD，后缀是BCDE、CDE、DE、E，其临时匹配是0；

ABCDEA前缀是A、AB、ABC、ABCD、ABCDE，其后缀是BCDEA、CDEA、DEA、EA、A，其

临时匹配是1（A）；

ABCDEAB前缀是A、AB、ABC、ABCD、ABCDE、ABCDEA，后缀是BCDEAB、CDEAB、DEAB、EAB、AB、A，其临时匹配是2（AB）；

ABCDEABC前缀是A、AB、ABC、ABCD、ABCDE、ABCDEA、ABCDEAB后缀是BCDEABC、CDEABC、DEABC、EABC、ABC、BC、C，其临时匹配是3（ABC）。

即移动到：

FBC ABCDAB ABCDABCDABYW

        ABCDABY

（4）空格与Ｃ不匹配，那就还要继续往后移，这时已匹配的字符数为2（"AB"），"部分匹配值"为0。所以，移动位数为 2，于是将搜索词向后移2位。

FBC ABCDAB ABCDABCDABYW

          ABCDABY  

（5）A和空格不匹配，继续往后移动一位。

FBC ABCDAB ABCDABCDABYW

           ABCDABY

（6）逐个比较，找到上下不同的字符，发现Y和C不同，那按照（3）的算法，那移动位数是6-2=4.

FBC ABCDAB ABCDABCDABYW

           ABCDABY

（7）最后还是逐个比较，完全匹配。此时发现F中还有一位没有比较，继续使用步骤（3）的算法，移动位数：7-0=7。

FBC ABCDAB ABCDABCDABYW

               ABCDABY

（8）再次比较W和A，还是不匹配，往后移动一位，发现比较完了，完成搜索。

　　以上是KPM算法的理解，关于这个算法的实现，将在下篇博客中记录，关于本文，欢迎吐槽............