主要讨论的就是字符串匹配的问题。

暴力匹配

用下标i索引文本串s，用下标i索引模式串p，思路为：

1. 如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；
2. 如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。

JavaScript代码如下：

function violentMatch(s, p) {
    console.time('violentMatch');
    var p_len = p.length,
        s_len = s.length,
        result = -1;
        i = 0,
        j = 0;
    while (i < s_len && j < p_len) {
        if (s[i] == p[j]) {
            i++;
            j++;
        } else {
            // i回溯
            i = i - j + 1;
            // j置0
            j = 0;
        }
    }
    if (j == p_len) {
        result = i - j;
    } 
    console.timeEnd('violentMatch');
    return result;
}

暴力匹配有个性能问题：不管任何情况，一旦失配i就回溯，然后继续往下走，这个过程中会导致很多必然失配的步骤。那有没有一种算法让i 不往回退，只需要移动j 即可。答案是肯定的，这就是KMP要解决的问题，利用之前已经部分匹配这个有效信息，保持i 不回溯，通过修改j 的位置，让模式串尽量地移动到有效的位置。

KMP算法

算法流程：

1. 如果j == -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；
   • j==0，表示跳到模式串的开头字符
   • j==-1，表示跳转到模式串开头，且原串移动一位
2. 如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。

next数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next [j] = k，代表j 之前的字符串中有最大长度为k的相同前缀后缀。初值赋1。

KMP的next 数组相当于告诉我们：当模式串中的某个字符跟文本串中的某个字符匹配失配时，模式串下一步应该跳到哪个位置。如模式串中在j 处的字符跟文本串在i 处的字符匹配失配时，下一步用next [j] 处的字符继续跟文本串i 处的字符匹配，相当于模式串向右移动 j - next[j] 位。

转换成代码表示为：

function kmpSearch(source, target) {
    console.time('kmpSearch');
    var i = 0,
        j = 0,
        result = -1;
        next = [],
        tar_len = target.length,
        sou_len = source.length;
    calNext(target, next);
    while (i < sou_len && j < tar_len) {
        if (j == -1 || source[i] == target[j]) {
            i++;
            j++
        } else {
            j = next[j];
        }
    }
    if (j == tar_len) {
        result = i - j;
    }
    return result;
    console.timeEnd('kmpSearch');
}

这样一来，kmp算法不同于暴力匹配，失配时i不回溯，模式串也不是简单的右移一位，而是移动j-next[j]位。

不难看出kmp复杂度O(m+n)

next数组

得到next数组时需要明白next数组的意义和规则：

• 意义：失配时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next值。
• 规则：代表当前字符之前的字符串中，有多大长度的相同前缀后缀(最大长度表)

计算规则：用k表示前缀，用j表示后缀

1. 如何p[k]==p[j]，则很简单，next[j+1] = next[j] +1 = k+1；
2. 如果p[k]!=p[j]，这就比较复杂了，存在一个递归前缀索引问题，怎么说呢？就是有这么一种情况，比如DABCDABDE，当计算E的next值时，DABCDABD前缀走到最后一步时C和D失配，但是D确实个第一个D匹配的！因此如果p[k]!=p[j]时，令k=next[k]，如果此时p[k] == p[j]，则next[ j + 1 ] = next[k] + 1，否则继续递归前缀索引k = next[k]，如果一直失配，则直到k = -1才退出递归，此时next[j+1] = 0。
   • 为何递归前缀索引k = next[k]，就能找到长度更短的相同前缀后缀呢？此过程相当于模式串的自我匹配，所以不断的递归k = next[k]，直到要么找到长度更短的相同前缀后缀，要么没有长度更短的相同前缀后缀。

因此我们可以得到求next的函数

function calNext(target, next) {
    // 赋初值
    next[0] = -1;
    var tar_len = target.length;
    var k = -1;
    var j = 0;
    while (j < tar_len) {
        if (k == -1 || target[k] == target[j]) {
            k++;
            j++;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
}

上述其实是基于最大长度表计算而来，这也是为什么当匹配时，先k++;j++，然后next数组再赋值的原因，那么为什么可以如此且为什么这么做呢？

1. j 从0开始计数，那么当数到失配字符时，j 的数值就是已匹配的字符数；
2. 由于next 数组是由最大长度值表整体向右移动一位（且初值赋为-1）得到的，那么失配字符的上一位字符所对应的最大长度值，即为当前失配字符的next值。
3. 为何本文不直接利用next 数组进行匹配呢？因为next数组不好求，而一个字符串的前缀后缀的公共元素的最大长度值很容易求。

next数组优化

上面逻辑看似没什么问题，但是我们忽略了一个问题。对于模式串abab的问题，next数组为[-1,0,0,1]，如果末尾b失配，那么按照规则而言，模式串需要移动两位，但是p[1]=p[3]，因此肯定必然再次失配。

问题出在不该出现p[j] = p[ next[j] ]。为什么呢？理由是：当p[j] != s[i] 时，下次匹配必然是p[ next [j]] 跟s[i]匹配，如果p[j] = p[ next[j] ]，必然导致后一步匹配失败（因为p[j]已经跟s[i]失配，然后你还用跟p[j]等同的值p[next[j]]去跟s[i]匹配，很显然，必然失配），所以不能允许p[j] = p[ next[j ]]。如果出现了p[j] = p[ next[j] ]咋办呢？如果出现了，则需要再次递归，即令next[j] = next[ next[j] ]。优化后的calNext函数如下：

function calNext(target, next) {
    // 赋初值
    next[0] = -1;
    var tar_len = target.length;
    var k = -1;
    var j = 0;
    while (j < tar_len) {
        if (k == -1 || target[k] == target[j]) {
            k++;
            j++;
            if (target[j] != target[k])  
                next[j] = k;
            else
                // 因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]  
                next[j] = next[k];  
        } else {
            k = next[k];
        }
    }
}

优化过后的对于abab型的模式串。next数组也是对称结果，-1,0,-1,0。

更多

• BM算法
• Sunday算法

暂时不想看了，真能说牛逼！

资料

• 从头到尾彻底理解KMP