钛节点

KMP算法的青铜版本

发表@2018-11-14 21:56:03

更新@2023-01-21 22:47:40

其实KMP哪儿有什么青铜版本，KMP就是KMP，标题里之所以有KMP，完全是为了装逼。

首先说KMP是为了解决字符串查找匹配的问题而诞生的。比如你跑路去面试了，面试官装了一波儿逼：“假设有A字符串gow.google.com，B字符串goo，那么你研究一个算法搞出来字符串B在字符串A中的位置”。

“卧槽，这种低级问题还用问，难道你不知道strpos()函数吗？”

“你先回家等通知吧。。。”

作为泥腿子，你怎么会可能知道除了strpos函数之外如何实现字符串查找，反正一开始我是不会的，strpos()函数复制粘贴一把梭！

![](https://ti-node.com/static/upload/6468456412899966976)

假如PHP里没有strpos函数，如何才能搞定这一把梭？按照一般套路说来，首先先想一个怂办法，也就是贯彻“先快速上线实现，后面快速优化迭代”。其实怂办法反正我是想不到太高端的，就是循环遍历，大概类似于下面的节奏，你们感受一下。

--------------
第一次循环：
A：g o w . g o o g l e . c o m
B：g o o
B串中的第一个字符g先和A串中的第一个字符g对比，对上眼了；然后B串的第二个字符o和A串中的第二个字符o对比，又对上眼了；然后B串中的第三个字符o和A串中的第三个字符w对比，劈叉了，本次循环终止，将B字符串整体向后移动。

-----------
第二次循环（注意我用x表示一个占位符，没有实际作用）：
A：g o w . g o o g l e . c o m
B：x g o o
这次循环就简单的很了，B串中的第一个字符g和A串中的第二个字符o一比，直接劈叉，终止对比，直接进入下一轮循环。

----------
第三次循环（注意我用x表示一个占位符，没有实际作用）：
A：g o w . g o o g l e . c o m
B：x  x  g o o
B串的第一个字符g与A串的第三个字符w一比，再次劈叉，终止本次循环。

----------
第四次循环（注意我用x表示一个占位符，没有实际作用）：
A：g o w . g o o g l e . c o m
B：x  x x  g o o
B串的第一个字符g与A串的第四个字符 " . " 一比，继续劈叉，终止本次循环。

----------
第五次循环（注意我用x表示一个占位符，没有实际作用）：
A：g o w . g o o g l e . c o m
B：x  x x x g o o
B串的第一个字符g与A串的第五个字符g对比，对眼了；然后B串的第二个字符o与A串的第六个字符o对比，对眼了；最后B串的第三个字符o与A串的第七个字符g对比，最终对眼，bingo！

思路就是这么个思路，虽然愚蠢了点儿，但是话说回来：又不是不能用！

下面得砌砖头了，画图纸二狗子都会，真要砌砖头怕是不如画图纸这么轻松愉悦。。。 。。。

![](https://ti-node.com/static/upload/9968ce1b9d16fdfaa5aecd6bbe8f8c5496ee7bff.gif)

```
<?php
$str = 'www.google.com';
$kmp = '.g';

$str_len = strlen( $str );
$kmp_len = strlen( $kmp );

if ( $kmp > $str_len ) {
  exit();
}

for ( $outer = 0; $outer < $str_len; $outer++ ) {
  if ( ( $outer + $kmp_len ) > $str_len ) {
    exit( 'length exceed.'.PHP_EOL );
  }
  $temp_outer = $outer;
  for ( $inner = 0; $inner < $kmp_len; $inner++ ) {
    if ( $kmp[ $inner ] == $str[ $temp_outer ] ) {
      // 如果inner已经到最后一位了
      if ( $inner == ( $kmp_len - 1 ) ) {
        exit( "bingo : {$outer}".PHP_EOL );
      }
      $temp_outer++;
    }
  }
}
```

一些书上称上面这种思路的字符串匹配算法叫做“朴素模式匹配算法”，反正就是这么个名字，与KMP并没有什么关系，其实本篇通篇都和KMP没什么关系，那么为什么标题里还要提KMP，我不是说了么，为了装逼。。。

首先说KMP是三个老头的英文名简称，依次是Knuth、Morris、Pratt，翻译过来大概就是“库努斯”、“莫里斯”、“普兰特”的意思。上面这个算法我们分析一下，实际上是很愚蠢的，如果说A串和B串是下面这种的，那这种算法简直让人折寿。

A：abcabcabcabcabo
B：abo

你们自己用上面的A、B串推演一下，这种算法多么悲催。。。

假设A串的长度为M，B串的长度N，最好的情况下第一次就可以匹配上，最垃圾的情况下需要M+N次才能完全匹配（也就是上面这种情况），综上平均次数为(M+N)/2，如果大O阶推一下的话时间复杂度为O(M+N)。

而KMP就是一种比较屌的字符串匹配算法，总之就是屌，能让你用更短时间就能搞定子串的位置，可谓是字符匹配届中的一夜七次郎、时间就是短！先消化一波儿这种蠢货用的办法，下篇准备比较屌KMP。