字符串匹配KMP

2018-12-04 本文已影响0人 _旁观者_

本文内容学习自字符串匹配的KMP算法

如果有一个字符串BBC ABCDAB ABCDABCDABDE ，要查找里面是否有搜索串 ABCDABD。
那实现代码最简单的方法就是 两层循环 ，以此比较。

字符串比较步骤

1 字符串的第一位和搜索串的第一位不同，搜索串后移一位，继续比较
2 字符串的第一位和搜索串的第一位相同，比较字符串的第二位和搜索串的第二位是否相同。直到全部相同，查找结束。否则搜索串后移一位，继续比较

这样做法肯定能实现，但是太耗性能

KMP

kmp 算法的优点就是简化了比较的次数，不用逐步比较

字符串比较步骤

1 字符串的第一位和搜索串的第一位不同，搜索串后移一位，继续比较（与上面相同）
2 字符串的第一位和搜索串的第一位相同，比较字符串的第二位和搜索串的第二位是否相同。直到全部相同，查找结束。否则搜索串后移（这里做了优化），继续比较

字符串的第一位和搜索串的第一位不同，搜索串后移一位继续比较。。。直到

这里已经有六位相同

这里已经有六位数是相同的了，如果按照普通的比较，只能后移一位重新比较
这里 kmp 算法会借助已匹配的这一位计算后移的位数

kmp 位移数计算

对已匹配的字符串计算步骤

按照一般方法是这样比较的

kmp 位移数会计算移动步数
我们的目的是找到搜索串全匹配的位置，可以这样优化位移数

字符串已经有6个字符串与 搜索串中的6个字符串相同，只要关心搜索串中已匹配的6个字符串即可
- 假设搜索串中已匹配的6个字符串全不相同，就可以移动 全部的相同字符串
- 如果搜索串中已匹配的6个字符串有相同的，就可以移动 部分字符串

因此：

位移数 = 已匹配的长度 - 元素中重复出现的长度

步骤图如下

步骤图.png

匹配数代码实现

建立搜索串对应长度中的重复字符串

        let startTimestamp=new Date().getTime()
        let string = 'BBC ABCDAB ABCDABCDABDE'
        let keyString = 'ABCDABD'
        let arr = []
        // 建立搜索关键字数组
        let findRelation = function  () {
            let searchArr = []
            let relationArr = []
            for (let i = 0; i < keyString.length; i++) {
                searchArr.push(keyString.slice(0, i+1))
            }
            for (let i = 0; i < searchArr.length; i++) {
                let sameFlag = 0 // 共有长度计数
                if (searchArr[i].length === 1) { // 字符串长度为1时，共有长度为0
                    relationArr.push({goal: searchArr[i], sameFlag: sameFlag})
                }else {
                    let string =searchArr[i]
                    let frontArr = []
                    let backArr = []
                    // 处理正反两个数组，并且比较，获取共有数据长度
                    for (let i = 0; i < string.length-1; i++) {
                        frontArr.push(string.slice(0, i+1))
                        backArr.push(string.slice(-(i+1)))
                    }
                    for (let i = 0; i < frontArr.length; i++) {
                        if(frontArr[i] === backArr[i]) {
                            sameFlag = backArr[i].length
                        }
                    }
                    relationArr.push({goal: searchArr[i], sameFlag: sameFlag})
                }
            }
            return relationArr
        }

匹配数.png

建立匹配数后，就可以进行循环比较了

KMP 代码

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Document</title>
</head>
<body>
    <script>
        let startTimestamp=new Date().getTime()
        let string = 'BBC ABCDAB ABCDABCDABDE'
        let keyString = 'ABCDABD'
        let arr = []
        // 建立搜索关键字数组
        let findRelation = function  () {
            let searchArr = []
            let relationArr = []
            for (let i = 0; i < keyString.length; i++) {
                searchArr.push(keyString.slice(0, i+1))
            }
            for (let i = 0; i < searchArr.length; i++) {
                let sameFlag = 0 // 共有长度计数
                if (searchArr[i].length === 1) { // 字符串长度为1时，共有长度为0
                    relationArr.push({goal: searchArr[i], sameFlag: sameFlag})
                }else {
                    let string =searchArr[i]
                    let frontArr = []
                    let backArr = []
                    // 处理正反两个数组，并且比较，获取共有数据长度
                    for (let i = 0; i < string.length-1; i++) {
                        frontArr.push(string.slice(0, i+1))
                        backArr.push(string.slice(-(i+1)))
                    }
                    for (let i = 0; i < frontArr.length; i++) {
                        if(frontArr[i] === backArr[i]) {
                            sameFlag = backArr[i].length
                        }
                    }
                    relationArr.push({goal: searchArr[i], sameFlag: sameFlag})
                }
            }
            return relationArr
        }
        let findStringOfIndex = function () {
            arr = findRelation() // 已建立的索引匹配值
            let sameStringLength = 0 // 已匹配的字符数
            let index = 0 // 匹配位置索引
            for (let  i = 0; i < string.length; i++) {
                for (let j = 0; j < keyString.length; j++) {
                    if (string[i] !== keyString[j]) {
                        if(sameStringLength) {
                            i = i + (sameStringLength - arr[sameStringLength - 1]['sameFlag'])
                            sameStringLength = 0
                        }
                        break
                    }else {
                        sameStringLength ++
                        i++
                    }
                }
                if(sameStringLength === keyString.length) {
                    index = i - keyString.length
                    sameStringLength = 0
                    break
                }
            }
            if(index) {
                alert('匹配位置索引为' + index)
            }else {
                alert('无匹配项用时')
            }
        }
        findStringOfIndex()
    </script>
</body>
</html>

ps: 关于 KMP 应该还有优化方法

未匹配的字符串和`搜索串`中的没有相同的。

此时可以移动整个字符串的位置

字符串匹配KMP

字符串比较步骤

KMP