KMP

KMP算法

KMP: O(M+N)

基本的匹配算法是需要 N*M 次比较，而我们希望从主串的i点开始比较，向后比较了k个字符时失败，那么下一次匹配的时候我们是否需要从i+1开始重新匹配？答案是否定的，我们的next函数就是寻找下个匹配的开始位置。假设我们在i+k1处能够匹配成功，可知findStr.substring(0,k) == findStr.substring(j - k,j)，反过来，我们就需要寻找满足findStr.substring(0,k) == findStr.substring(j - k,j)的k值，也就是我们在findStr下标j处失败时应该重新开始匹配的点。在KMP算法中我们会使用i,j两个指针，其中i会指向当前主串匹配到的位置，j指向模式串匹配到的位置，其中i是只会增加的，即每次重新匹配时i要么不变，要么加1。而j则根据模式串自身计算出的next向量的对应值，在每次重新匹配时动态设置。当我们在进行匹配时，假设在匹配字串originStr下标i，模式串findStr下标j处失败，可以得到如下处理：(1)如果j == 0，即在第一个字符处匹配失败，则设置i = i + 1，j = 0进行新一轮匹配。(2)如果j > 0，那么假设下一轮匹配在originStr下标i，findStr下标k处开始，显而易见可以得到k < j并且findStr.substring(0,k) == findStr.substring(j - k,j)，就如下图所示：

换言之，当我们需要计算在i，j处匹配失败之后下一轮开始的下标时，如果findStr.substring(0,k) == findStr.substring(j - k,j)，并且j > k时，我们就需要将下一轮的开始的j进行如下赋值：j = k。这里的k，即是我们编程时通过计算得到的next数组中所指示的值。综上所述，KMP算法的核心即是计算字符串findStr每一个位置之前的字符串的前缀和后缀公共部分的最大长度(不包括字符串本身，否则最大长度始终是字符串本身)。获得findStr每一个位置的最大公共长度之后，就可以利用该最大公共长度快速和字符串originStr比较。当每次比较到两个字符串的字符不同时，我们就可以根据最大公共长度将字符串findStr向前移动(已匹配长度-最大公共长度)位，接着继续比较下一个位置。事实上，字符串findStr的前移只是概念上的前移，只要我们在比较的时候从最大公共长度之后比较findStr和originStr即可达到字符串f前移的目的。

next计算

理解了kmp算法的基本原理，下一步就是要获得字符串f每一个位置的最大公共长度。这个最大公共长度在算法导论里面被记为next数组。在这里要注意一点，next数组表示的是长度，下标从1开始；但是在遍历原字符串时，下标还是从0开始。假设我们现在已经求得next[1]、next[2]、……next[i]，分别表示长度为1到i的字符串的前缀和后缀最大公共长度，现在要求next[i+1]。由上图我们可以看到，如果位置i和位置next[i]处的两个字符相同(下标从零开始)，则next[i+1]等于next[i]加1。如果两个位置的字符不相同，我们可以将长度为next[i]的字符串继续分割，获得其最大公共长度next[next[i]]，然后再和位置i的字符比较。这是因为长度为next[i]前缀和后缀都可以分割成上部的构造，如果位置next[next[i]]和位置i的字符相同，则next[i+1]就等于next[next[i]]加1。如果不相等，就可以继续分割长度为next[next[i]]的字符串，直到字符串长度为0为止。由此我们可以写出求next数组的代码(java版)：

public static int[] getNext(String findStr) {

    //模式字符串的长度
    int len = findStr.length();

    int j = 0;

    //next表示长度为i的字符串前缀和后缀的最长公共部分，从1开始
    //next[1]表示长度为1的字符串前缀和后缀的最长公共部分,也就是在字符串下标1处匹配失败所需要回退到的位置
    int next[] = new int[len + 1];

    //初始化前两个数值为0
    next[0] = next[1] = 0;

    //从字符串下标1开始匹配
    //ababcd
    for (int i = 1; i < len; i++) {
        //在第 i 次循环中,我们计算的是 next[i + 1]的值,因为在考虑 i + 1位置时,需要将第 i 个字符进行考虑
        //j在每次循环开始都表示next[i]的值，同时也表示需要比较的下一个位置
        while (j > 0 &&
                //直到找到离起点最近的一个与i字符相等的下标
                findStr.charAt(i) != findStr.charAt(j)
                ) {
            //不断分割子字符串
            //以abcdcabcd为例,next[7] = 2,这样就找到了离起点最近的那个c
            j = next[j];
        }

        //如果第 i 个字符与第 j 个字符相等,则把长度加1
        //这个if是判断第一个字符串与第i个字符串是否相等,相等的话还是要加1的
        //在j>0的情况下,这个是必然相等的
        if (findStr.charAt(i) == findStr.charAt(j)) j++;

        //将当前选定的j赋值给next[i+1]
        next[i + 1] = j;
    }

    return next;
}

KMP

KMP算法

KMP: O(M+N)

next计算

Links