算法-KMP

算法介绍

KMP字符串匹配算法。

移动位数 = 已匹配的字符数 – 对应的部分匹配值

《部分匹配表》怎么得出

两个概念：”前缀”和”后缀”：

“前缀”指除了最后一个字符以外，一个字符串的全部头部组合；

”后缀”指除了第一个字符以外，一个字符串的全部尾部组合。

“部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。

以”ABCDABD”为例，

－　”A”的前缀和后缀都为空集，共有元素的长度为0；

－　”AB”的前缀为[A]，后缀为[B]，共有元素的长度为0；

－　”ABC”的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；

－　”ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；

－　”ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为”A”，长度为1；

－　”ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为”AB”，长度为2；

－　”ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

“部分匹配”的实质是，有时候，字符串头部和尾部会有重复。比如，”ABCDAB”之中有两个”AB”，那么它的”部分匹配值”就是2（”AB”的长度）。搜索词移动的时候，第一个”AB”向后移动4位（字符串长度-部分匹配值），就可以来到第二个”AB”的位置。

Go实现

package main

import "fmt"

func main() {

  s := "11xxabcabbadcaddab1cabxd"

  t := "abcab"

  pos := kmp(s, t, 1)

  fmt.Println(pos)
}

func getNext(t string) []int {
  var next = make([]int, len(t)+1)
  i, j := 1, 0

  next[1] = 0

  for i < len(t) {
    if j == 0 || t[i] == t[j] {
      i++
      j++
      next[i] = j
    } else {
      j = next[j]
    }
  }
  return next

}

func kmp(s string, t string, pos int) int {
  i := pos
  j := 1

  next := getNext(t)
  fmt.Println(next)

  for i < len(s) && j < len(t) {
    if j == 0 || s[i] == t[j] {
      i++
      j++
    } else {
      j = next[j]
    }
  }

  if j >= len(t) {
    return i - len(t)
  }
  return -1
}

PHP实现

// KMP算法实现
function indexOf($target,$pattern,$start){  
    if($target && $pattern && strlen($target)>strlen($pattern)){  
        $i = $start;  
        $j = 0;  
        $next = getNext($pattern);  
        while ($i<strlen($target)){  
            if ($j==-1||$target{$i}==$pattern{$j}){  
                $i++;$j++;    
            }else  
                $j = $next[$j];  
            //echo "i:$i,j:$j";  
            if ($j==strlen($pattern))  
                return 'offset: '.($i-$j);  
        }
    }
    return -1;  
}
// 获取模式串的next数组的函数  
function getNext($pattern){  
    $j=0;$k=-1;   
    $next[0] = -1;  
    while ($j<strlen($pattern)-1){  
        if ($k==-1||$pattern{$j} == $pattern{$k}){  
            $k++;$j++;  
            $next[$j] = $k;  
        }else  
            $k = $next[$k];  
    }  
    return $next;
}
$strs = "BBC ABCDAB ABCDABCDABDE";
$mystr = "ABCDABD";
echo indexOf($strs,$mystr,0);

参考：

字符串匹配的KMP算法

算法