字符串HERE IS A SIMPLE EXAMPLE
搜索串 EXAMPLE。
在比较之前，先介绍两个概念
- 坏字符 （
字符串和搜索串对应不相同就是坏字符）
坏字符.png
- 好字符 （
字符串和搜索串对应相同就是好字符）
好字符.png
坏字符串比较
有两种情况 （搜索串中是否包含坏字符）
-
搜索串包含坏字符时， 移动到相应的位置即可（如果多个的话，移动到最近的一个）
-
搜索串不包含坏字符时， 移动整个搜索串，如图
整个移动.png
好字符串比较 （同上面类似）
-
搜索串不包含好字符，移动应该是这样
-
搜索串部分包含好字符时
好字符串只有E有对应的，移动到'' EXA '' 的E的位置
-
搜索串整个包含好字符时
在同时存在好字符和坏字符时，选择移动步数大的，如
此时选择好字符移动
整个移动规则
整个移动步骤.png
代码实现
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Document</title>
</head>
<body>
<script>
function BM (string, searchString) {
this.string = string // 字符串
this.searchString = searchString // 搜索词
this.lengthOfSearchString = this.searchString.length
this.badStringIndex = 0 //搜索词中的上一次出现位置
this.indexSearchString = 0 // 坏字符的位置
this.sameStringLength = 0 // 已匹配的字符数
this.index = 0 // 匹配位置索引
}
BM.prototype.init = function () {
this.search()
}
BM.prototype.search = function () {
var _that = this
if (_that.lengthOfSearchString < _that.string.length) {
for (let i = _that.lengthOfSearchString - 1; i < _that.string.length; i++) {
for (var j = _that.lengthOfSearchString - 1; j >= 0; j--) {
// 由于要多次比较， 缓存一下
let tempString = _that.string[i-(_that.lengthOfSearchString - 1-j)]
// 匹配搜索词，不同的话根据好、坏字符计算移动步数，相同的话sameStringLength + 1
if (_that.searchString[j] !== tempString) {
if (j === this.lengthOfSearchString-1) {
console.log('坏字符规则')
i = _that.badStep(i, tempString, j)
}else {
console.log('比较好坏字符规则')
// 比较好坏字符规则，选出移动步数大的
i = Math.max(_that.badStep(i, tempString, j), _that.goodStep(i, tempString, j))
}
break
}else {
_that.sameStringLength++
}
}
// 判断是否全部匹配
if(_that.sameStringLength === _that.searchString.length) {
_that.index = i - _that.searchString.length +1
_that.sameStringLength = 0
break
}else {_that.sameStringLength = 0}
}
}
if(_that.index) {
alert('匹配位置索引为' + _that.index+ _that.string[_that.index])
}else {
alert('无匹配项')
}
}
BM.prototype.badStep = function (i, tempString, j) { // 由坏字符计算移动步数
this.badStringIndex = this.searchString.indexOf(tempString)
this.indexSearchString = j
return (i + (this.indexSearchString - this.badStringIndex) - 1)
}
BM.prototype.goodStep = function (i, tempString, j) { // 由好字符计算移动步数
let arr = []
let maxStep = {index: -1, stringIndex: -1}
for (let m = j+1; m < this.lengthOfSearchString; m++) {
let goodString = this.searchString.substr(m) // 好字符串
let leftGoodString = this.searchString.substr(0,m) // 好字符串左侧的字符串
let index = leftGoodString.indexOf(goodString)
if (index > -1) {
arr.push({index: index, stringIndex: m})
}
}
if (arr.length === 0) { // 没有匹配的字符串移动整个字符串
return (i + this.lengthOfSearchString)
}else { // 有匹配的字符串,
arr.forEach(item => {
if(item['stringIndex'] - item['index'] > maxStep['stringIndex'] - maxStep['index']) {
maxStep['index'] = item['index']
maxStep['stringIndex'] = item['stringIndex']
}
})
return (i + maxStep['stringIndex'] - maxStep['index'])
}
}
let bm = new BM('HERE IS A SIMPLE EXAMPLE', 'EXAMPLE')
bm.init()
</script>
</body>
</html>
网友评论