javascript实现字符查询之kmp算法

- 日理万妓 2021-12-13 16:01 82阅读 0赞

## KMP算法 ##

### 定义 ###

Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。

下面先直接给出KMP的算法流程（如果感到一点点不适，没关系，坚持下，稍后会有具体步骤及解释，越往后看越会柳暗花明☺）：

*  假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置
    
     *  如果j = -1，或者当前字符匹配成功（即S\[i\] == P\[j\]），都令i++，j++，继续匹配下一个字符；
     *  如果j != -1，且当前字符匹配失败（即S\[i\] != P\[j\]），则令 i 不变，j = next\[j\]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next \[j\] 位。
        
         *  换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值（next 数组的求解会在下文的[3.3.3节][3.3.3]中详细阐述），即移动的实际位数为：j - next\[j\]，且此值大于等于1。

很快，你也会意识到next 数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next \[j\] = k，代表j 之前的字符串中有最大长度为 *k*  的相同前缀后缀。

此也意味着在某个字符失配时，该字符对应的next 值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到next \[j\] 的位置）。如果next \[j\] 等于0或-1，则跳到模式串的开头字符，若next \[j\] = k 且 k > 0，代表下次匹配跳到j 之前的某个字符，而不是跳到开头，且具体跳过了k 个字符。

/* kmp 算法的javascript实现
    * 参考文档－》https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html
    * 算法复杂度O(n+m)
    * 定义
        Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。
        下面先直接给出KMP的算法流程（如果感到一点点不适，没关系，坚持下，稍后会有具体步骤及解释，越往后看越会柳暗花明☺）：
    假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置
    如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；
    如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。
    换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值（next 数组的求解会在下文的3.3.3节中详细阐述），即移动的实际位数为：j - next[j]，且此值大于等于1。
        很快，你也会意识到next 数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next [j] = k，代表j 之前的字符串中有最大长度为k 的相同前缀后缀。
        此也意味着在某个字符失配时，该字符对应的next 值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到next [j] 的位置）。如果next [j] 等于0或-1，则跳到模式串的开头字符，若next [j] = k 且 k > 0，代表下次匹配跳到j 之前的某个字符，而不是跳到开头，且具体跳过了k 个字符。
    */
     function getNext(p) {
        const next = [-1];
        let k = -1;
        let j = 0;
        let pLen=p.length;
    
        while (j < pLen-1) {
            //p[k]表示前缀，p[j]表示后缀
            if (k == -1 || p[j] == p[k])
            {
                ++j;
                ++k;
                //较之前next数组求法，改动在下面4行
                if (p[j] != p[k])
                    next[j] = k;   //之前只有这一行
                else
                //因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]
                    next[j] = next[k];
            }
            else
            {
                k = next[k];
            }
        }
    
        return next;
    
    }
    
    function KmpSearch(s, p) {
        let i = 0;
        let j = 0;
    
        const sLen = s.length;
        const pLen = p.length;
    
        const next = getNext(p);
    
        while (i < sLen && j < pLen) {
            //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
            if (j === -1 || s[i] === p[j]) {
                i++;
                j++;
            } else {
                //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
                //next[j]即为j所对应的next值
                j = next[j];
            }
        }
    
        return j === pLen ? i - j : -1;
    }
    
    //demo test
    console.log(KmpSearch('asdfasdfsadf','sdfsd'))

转载于:https://www.cnblogs.com/caoke/p/10818438.html

[3.3.3]: http://blog.csdn.net/v_july_v/article/details/7041827#t9