mink 小屋主页归档标签分类关于
字符串匹配
|数据结构|

朴素匹配算法

朴素匹配算法是对目标字符串和模板字符串的一一匹配。如果匹配得上,下标向右移一位, 否则清空并重新开始匹配。

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
const match = (target, pattern) => {
  let [i, j] = [0, 0]
  let [n, m] = [target.length, pattern.length]
  while (i < n && j < m) {
    if (target[i] == pattern[j]) {
      console.log(
        `匹配的元素: target[${i}]=${target[i]}, pattern[${j}]=${pattern[j]}`
      )
      i += 1
      j += 1
    } else {
      console.log(
        `不匹配的元素: target[${i}]=${target[i]}, pattern[${j}]=${pattern[j]}`
      )
      i = i - j + 1
      j = 0
    }
  }
  if (j == m) {
    return i - j
  }
  return -1
}
;(function main() {
  let target = 'abb abad abac'
  let pattern = 'abac'
  console.log('target', target)
  console.log('pattern', pattern)
  match(target, pattern)
})()

KMP 匹配算法

kmp 是通过已知匹配的字符进行移位的算法，位移数是通过已匹配的字符串的前缀和后缀元素集合中最长子元素长度。详解

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/**
 * 获取模板字符串所有前缀子串
 * @param {String} pattern 模板字符串
 */
const getPrefix = pattern => {
  let list = []
  for (let i = 0; i < pattern.length - 1; i++) {
    let s = pattern.slice(0, i + 1)
    if (s.length > 0) {
      list.push(s)
    }
  }
  return list
}

/**
 * 获取模板字符串所有后缀子串
 * @param {String} pattern 模板字符串
 */
const getSuffix = pattern => {
  let list = []
  for (let i = 0; i < pattern.length - 1; i++) {
    let s = pattern.slice(i + 1, -1)
    if (s.length > 0) {
      list.push(s)
    }
  }
  return list
}

/**
 * 获取偏移量
 * @param {String} pattern
 */
const patternNext = pattern => {
  let prefix = getPrefix(pattern)
  let suffix = getSuffix(pattern)
  let lst = prefix.filter(function(v) {
    return suffix.indexOf(v) > -1
  })
  let offset = -1

  for (let i = 0; i < lst.length; i++) {
    if (offset < lst[i].length) {
      offset = lst[i].length
    }
  }
  return offset
}

/**
 * kmp 匹配算法
 * @param {String} target
 * @param {String} pattern
 */
const match = (target, pattern) => {
  let [i, j] = [0, 0]
  let [n, m] = [target.length, pattern.length]
  while (i < n && j < m) {
    if (target[i] === pattern[j]) {
      console.log(
        `匹配元素: target[${i}]=${target[i]}, pattern[${j}]=${pattern[j]}`
      )
      i += 1
      j += 1
    } else {
      let offset = j - patternNext(pattern.slice(0, j))
      console.log(
        `不匹配元素: target[${i}]=${target[i]}, pattern[${j}]=${pattern[j]}`
      )
      console.log(`位移数: ${offset}`)
      i = i + offset
      j = 0
    }
  }
  if (j == m) {
    return i - j
  }
  return -1
}
;(function main() {
  let target = 'BBC ABCDAB ABCDABCDABDE'
  let pattern = 'ABCDABD'
  match(target, pattern)
})()
js