go – Page 2 – 计算机技术学习记录

kmp算法常用于优化字符串匹配，例如下面的问题：

有一个字符串a = “BBC ABCDAB ABCDABCDABDE”，我想知道，里面是否包含另一个字符串b = “ABCDABD”

一般的做法是循环比较。

func contain(a string, b string) bool {
  for i := 0; i < len(a); i++ {
    k := i
    for j := 0; j < len(b); {
      if b[j] == a[k] {
        if j == len(b)-1 {
          return true
        }
        j++
        k++
      } else {
        //匹配失败
        j = 0
        break;
      }
    }
  }
  return false
}

可以看到耗时O（n*m）,每一次失败都是从头逐个比较，特别对于ABCDAB多次重复匹配，kmp算法通过配置部分匹配表，减少这些重复匹配操作，从而达到优化效果。

KMP算法的精髓在于对已知信息的充分利用，理解kmp算法首先要了解一些概念：

字符串前缀，真前缀，后缀，真后缀，及前缀函数

举个例子，如字符串 ABCDABD，首先，不考虑空字符

前缀有A,AB,ABC,ABCD,ABCDA,ABCDAB,ABCDABD

真前缀有A,AB,ABC,ABCD,ABCDA,ABCDAB

同理可以理解后缀，真前（后）缀就是指不包含自身的前（后）缀

真后缀为BCDABD,CDABD,DABD,ABD,BD,D

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

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

这里指的是真前缀后缀
   －　"A"的前缀和后缀都为空集，共有元素的长度为0；
　　－　"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
　　－　"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；zh
　　－　"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。

前缀函数next[]是指某个字符串的最长真后缀同时也是它的前缀的子串长度。

array = {A, B, C, D, A, B, D}

next = {-1, 0, 0, 0, 1, 2, 0}

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

/**
部分匹配表
 */
func prefixFunction(str string) []int {
  sLen := len(str)
  prefix := make([]int, sLen)

  i := 0
  for j := 1; j < sLen-1; j++ {

    if str[j] == str[i] {
      i++
      prefix[j] = i
    } else {
      i = 0
    }
  }

  return prefix
}

/**
转移数组
 */
func obtainMoveFromPrefix(prefix []int) [] int {
  sLen := len(prefix)
  move := make([]int, sLen)
  move[0] = -1;
  for i := 0; i < sLen; i++ {
    if i == 0 {
      move[0] = -1;
    } else {
      move[i] = prefix[i-1]
    }
  }
  return move
}


func contain(a string, b string) bool {
  m, n := len(a), len(b)
  move := obtainMoveFromPrefix(prefixFunction(b))

  j := 0
  for i := 0; i < m; i++ {

    //有匹配的字符
    for j > 0 && b[j] != a[i] {
      j = move[j]
      if j < 0 {
        j = 0
      }
    }
    if b[j] == a[i] {
      j++
    }
    if j == n {
      return true
    }
  }

  return false

}

参考文章：

以前看js的时候，老是说，闭包闭包，但是一直搞不清楚，感觉就像个函数。最近看go，看到这篇文章，感觉有点明了。
Go by Example 中文：闭包
在我看来，闭包就是匿名函数使用了外部变量。

在wiki里的描述：
在计算机科学中，闭包（英语：Closure），又称词法闭包（Lexical Closure）或函数闭包（function closures），是引用了自由变量的函数。这个被引用的自由变量将和这个函数一同存在，即使已经离开了创造它的环境也不例外。
在没有闭包的语言中，变量的生命周期只限于创建它的环境。但在有闭包的语言中，只要有一个闭包引用了这个变量，它就会一直存在。清理不被任何函数引用的变量的工作通常由垃圾回收完成

package main

import "fmt"

func intSeq() func() int {
   i := 0
   return func() int {
      i = i + 1
      return i
   }
}

func main() {
   nextInt := intSeq();
   fmt.Println(nextInt())
   fmt.Println(nextInt())
   fmt.Println(nextInt())
   fmt.Println(nextInt())
   fmt.Println(nextInt())

   fmt.Println("-------")
   nextInt2 := intSeq();
   fmt.Println(nextInt2())

   fmt.Println("-------")
}

Category: go

kmp匹配字符串

闭包