KMP用于解决串匹配问题

图解KMP

KMP图解

KMP代码Go语言实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
func kmp(s1 string, s2 string) int {
   // 生成next数组
   // next 数组下标的含义为包括当前下标的字符串前缀长度
   // 也为模式串对应下标元素的下一个字符的下标
   next := getNext(s2)
   j := 0
   // i遍历文本串, j遍历模式串
   for i := 0; i < len(s1); i++ {
      // j > 0 防止死循环 因为前缀表[0] = 0
      // 若j ！= 0且不匹配 j跳到前缀的后一个元素下标进行匹配即next[j-1]
      // 直到匹配成功或到达模式串头 即j = 0
      for j > 0 && s1[i] != s2[j] {
         j = next[j-1]
      }
      // 若当前字符匹配成功
      // 为什么要加判断，因为可能存在j = 0的情况但没有匹配成功
      if s1[i] == s2[j] {
         j++
      }
      // 若整个模式串都匹配完成
      if j == len(s2) {
         return i - j + 1
      }
   }
   return -1
}

// 生成next数组
func getNext(s string) []int {
   // 生成next数组与KMP如出一辙
   // 只是next在遍历后缀(文本串)中在每次遍历前缀(模式串)字符匹配成功的时候都会记录
   // 而KMP在模式串匹配完成后返回
   j := 0
   next := make([]int, len(s))
   next[0] = j
   // i为遍历后缀(文本串)，j为遍历前缀()
   for i := 1; i < len(s); i++ {
      for j > 0 && s[i] != s[j] {
         // 会利用之前的next
         // 后缀已经有最长next[j-1]个元素与前缀相同
         // 一步步缩短相同的元素个数
         // 直到匹配成功 或 到达头退出此时i子串的最长相同前缀长度为默认值0
         j = next[j-1]
      }
      // 匹配成功j++
      if s[i] == s[j] {
         j++
      }
      // 记录当前 i子串的最长相同前缀长度
      next[i] = j
   }
   return next
}

例题

最大重复字符串

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
func maxRepeating(sequence string, word string) (ans int) {
    // 动归 dp[i] 代表了sequence[i+1-len(word):i+1]匹配成功word后的连续重复值
    // 若匹配成功 且 i < m 则dp[i] = 1 (此处为处理匹配成功但i - m不存在的情况)
    // 若匹配成功 且 i >= m 则dp[i] = dp[i - m] + 1
    dp := make([]int, len(sequence))
    // 生成next数组
    // next 数组下标的含义为包括当前下标的字符串前缀长度
    // 也为模式串对应下标元素的下一个字符的下标
    next := getNext(word)
    j := 0
    // i遍历文本串, j遍历模式串
    for i := 0; i < len(sequence); i++ {
        // j > 0 防止死循环 因为前缀表[0] = 0
        // 若j ！= 0且不匹配 j跳到前缀的后一个元素下标进行匹配即next[j-1]
        // 直到匹配成功或到达模式串头 即j = 0
        for j > 0 && sequence[i] != word[j] {
            j = next[j - 1]
        }
        // 若当前字符匹配成功
        // 为什么要加判断，因为可能存在j = 0的情况但没有匹配成功
        if sequence[i] == word[j] {
            j++
        }
        // 若整个模式串都匹配完成
        if j == len(word) {
            if i - len(word) < 0{
                dp[i] = 1
            } else {
                dp[i] = dp[i - len(word)] + 1
            }
            // 此处j已经是len(word) 那么next[j - 1]表示word整个字符串的前后缀长度
            // 此处跳转方便下一个字符利用后缀匹配
            j = next[j - 1]
        }
        if dp[i] > ans {
            ans = dp[i]
        }
    }
    return ans
}

// 生成next数组
func getNext(s string) []int {
    // 生成next数组与KMP如出一辙
    // 只是next在遍历后缀(文本串)中在每次遍历前缀(模式串)字符匹配成功的时候都会记录
    // 而KMP在模式串匹配完成后返回
    j := 0
    next := make([]int, len(s))
    next[0] = j
    // i为遍历后缀(文本串)，j为遍历前缀()
    for i := 1; i < len(s); i++ {
        for j > 0 && s[i] != s[j] {
            // 会利用之前的next
            // 后缀已经有最长next[j-1]个元素与前缀相同
            // 一步步缩短相同的元素个数
            // 直到匹配成功 或 到达头退出此时i子串的最长相同前缀长度为默认值0

            j = next[j-1]
        }
        // 匹配成功j++
        if s[i] == s[j] {
            j++
        }
        // 记录当前 i子串的最长相同前缀长度
        next[i] = j
    }
    return next
}