一、简介：

      KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。

二、原理：

      字符串： ABCBAACEDCBABADB

      搜索串： BABAD

一、计算搜索串部分匹配表

      ---- B 的前缀和后缀为空                                                         0

      ---- BA 前缀 B 后缀 A    交集为空                                             0

      ---- BAB 前缀 B BA 后缀 AB B交集为 B                                       1

      ---- BABA 前缀 B BA BAB 后缀 ABA BA A  交集为 BA                     2

      ---- BABAD 前缀 B BA BAB BABA 后缀 ABAD BAD AD D 交集为空     0

二、匹配计算

      1、ABCBAACEDCBABADB

            BABAD

       2、ABCBAACEDCBABADB

               BABAD                                           位移步数 = 已匹配字符数 - 对应匹配字符数 = 1 - 0 = 1

       3、ABCBAACEDCBABADB

                 BABAD 

       4、ABCBAACEDCBABADB

                   BABAD                                        位移步数 = 已匹配字符数 - 对应匹配字符数 = 2 - 0 = 2

       5、ABCBAACEDCBABADB

                        BABAD                                  此处一直后移一位，直至情况 6 出现

       6、ABCBAACEDCBABADB

                                   BABAD                            

三、程序语言：

    public function testKMP(){
        $be_search_str = 'ABCBAACEDCBABADB';
        $search_str = 'CBAA';
        $match_table = $this->_calculateMatchTable($search_str);
        $be_search_len = strlen($be_search_str);
        $search_len = strlen($search_str);
        for($i = 0; $i < $be_search_len; $i++){
            $j = 0;
            for($j = 0; $j < $search_len; $j++){
                $first_compare_word = substr($be_search_str, ($i+$j), 1);
                $compare_word = substr($search_str, $j, 1);
                if($first_compare_word === $compare_word){
                    if($j === ($search_len - 1) ){ echo ($i); exit; }
                    $step_value = $j - $match_table[($j-1)];
                }else{
                    if($step_value > 0){
                        $i = $i + $step_value;
                        $step_value = 0;
                    }
                    break;
                }
            }
        }
    }
    
    /**
     * 计算部分匹配表
     * @param type $search_str
     * @return boolean|int
     */
    private function _calculateMatchTable($search_str = ''){
        if($search_str == ''){ return FALSE; }
        $result = array();
        $result[] = 0;
        $str_len = strlen($search_str);
        if($str_len == 1){ return $result; }
        for($i = 2; $i <= $str_len; $i++){
            $calculate_str = substr($search_str, 0, $i);
            $calculate_count = 0;
            for($j = 1; $j < $i; $j++){
                $front_str = substr($search_str, 0, $j);
                $end_str = substr($search_str, (strlen($calculate_str) - $j), $j);
                if($front_str === $end_str){
                    $calculate_count += strlen($front_str);
                }
            }
            $result[] = $calculate_count;
        }
        return $result;
    }