算法思想

暴力优化

给定主串S和模式串P:
S:BBC ABCDAB ABCDABCDABDE
P:ABCDABD

暴力算法就是一个一个地匹配,失配了就模式串P整体后移一位,从头开始与主串S的失配字符的下一个字符开始匹配.
如图:

暴力算法做了太多无用功,如下图所示:
D与空格失配后,失配字符前的ABCDAB字串显然是配对的,换言之我们已经知道失配字符前的所有字符,那我们可以根据这些已知字符来跳过一些不可能的情况.

如上图,失配字符D之前的字串ABCDAB具有相同且最大的前后缀AB,故我们可以直接跳转使得失配字符前的字串的前缀(即模式串的前缀)与后缀(即主串的后缀)相对应.

也就是说,我们从头到尾假设每个字符失配,得到失配字符前的字串中相同的前缀和后缀,并记录下来,即可省略一大批步骤.那么怎么得到这个相同前后缀呢?

KMP步骤

  1. 寻找前后缀最长公共元素长度
    • 对于字串P = P[0] P[1] P[2] ... P[j-1] P[j],找其最长公共前后缀.
    • 如果有P[0] P[1] ... P[k] = P[j-k] P[j-k+1] ... P[j]即某条公共前后缀,那么对于一条包含这个公共前后缀的字串T来说,其最大公共前后缀长度是k+1,当然也可能是0…
    • 举例说明:
  2. 求next数组
    • 为了更好进行计算机计算,引入next数组,即失配发生后模式串P需要移动到哪个位置.
    • 其值是将第一步中的最大公共元素长度整体右移一位,并令初值为-1.
  3. 根据next数组进行匹配
    • 匹配失败,令j = next[j].
    • 即当模式串字串P[0] P[1] ... P[j-1]与主串字串... S[i-1]匹配失败,i与j匹配失败时, next[j] = k, 故将k移动到j位置, 让P[\k]与S[i]继续匹配.

机算next数组

  1. 对于值k,已经有P[0] P[1] ... P[k-1]与P[j-k] P[j-k+1] ... P[j-1],即next[j] = k.
  2. 怎么求next[j+1]?
    • 若P[k] == P[j], 那么公共长度可以加一, 即 next[j+1] = k + 1.
    • 若P[k] ≠ P[j]:
      • 若P[next[k]] == P[j], 则next[j+1] = next[k] + 1.
      • 若P[next[k]] ≠ P[j], 继续递归前缀索引k = next[k], 重复此过程知道条件成立. 这个过程相当于: 在字符P[j+1]前不存在长度k+1的前后缀相同, 那么是否有某个长度更小的前后缀相同呢?
        如果存在, 那么为什么是next[k]呢?
  3. 递归解释
    • 如下图所示,已知next[k] = 2(直接看出),那么因为P[k] == P[j], 故next[k+1] = 2 + 1 = 3.
    • 再如下图,P[k] ≠ P[j], 显然因为C不同于D, 所以ABC 跟 ABD不相同, 即字符E前的模式串没有长度为k+1的相同前缀后缀, 也就不能再简单的令：next[j + 1] = next[j] + 1 .所以,咱们只能去寻找长度更短一点的相同前缀后缀.
    • 那么为何要递归呢? 其实就是C与D不同, 但其前面相同(AB == AB, 这里假设是 ABAB = ABAB, 即 ABABC 与 ABABD 进行匹配), 那么只能是前缀AB(A)与后缀AB(D)匹配, 故要递归向前找长度更小的前缀.
  4. 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void getNext(char *P,int next[])
{

    int length = strlen(P);

    next[0] = -1;
    int k = -1;     //模式串类指针
    int j = 0;      //主串类指针
    
    // 模式串与主串相同 
    while(j < length-1)
    {
        if(k == -1 || P[k] == P[j]) //匹配成功,双双后移并记录当前模式串(即前缀)位置
        {
            ++k;     // 模式串后移
            ++j;     // 主串后移
            next[j] = k;   // 记录当前模式串(即前缀)位置,即失配时需要移动到的位置.
        }
        else
        {
            k = next[k];  // 回溯长度更小的前缀.
        }
    }
    up(length)cout<<next[i]<<" ";
}

next数组优化(nextval)

如下图,b和c失配后,模式串右移2,b和c又失配,这显然是算法缺陷.


问题出在不该出现P[j] = P[next[j]]
代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void getNextVal(char *P,int next[])
{

    int length = strlen(P);

    next[0] = -1;
    int k = -1;     //模式串类指针
    int j = 0;      //主串类指针
    
    // 模式串与主串相同 
    while(j < length-1)
    {
        if(k == -1 || P[k] == P[j]) //匹配成功,双双后移并记录当前模式串(即前缀)位置
        {
            ++k;     // 模式串后移
            ++j;     // 主串后移
            if(P[j] != P[k]) next[j] = k;
            else next[j] = next[k];
        }
        else
        {
            k = next[k];  // 回溯长度更小的前缀.
        }
    }
    up(length)cout<<next[i]<<" ";
}

手算next数组

考研不需要机算,故使用如下方法,在失配字符前画一条线,然后一步一步后退直到匹配或者过线.


串的下标从1开始.
下标0的位置是留给-1的,只要在下标0的位置加上0就是以-1开头,串下标从0开始计算的next数组.
计算nextval数组: 

1
2
3
for j from 2 to end:
    while p[j] == P[next[j]]:
        next[j] = next[next[j]]

因为我们只利用了失配元素之前的元素, 但其实失配元素也能利用起来, 也就是说失配元素失配后, 再下次跳转匹配时若还是相同元素就不可能匹配成功.
即当前元素若失配, 跳转到next对应元素, 若还是相同元素, 就应该继续跳到更短的公共前后缀对应位置.

通俗说就是在当前元素(从2到最后), 如果其next值对应的元素与当前元素相等, 就令当前next值等于对应元素的next值, 重复直到不相等(如当前坐标11,对应next=5,坐标5还是a,继续跳到坐标3依然是a,直到跳到坐标0不相等,所以next[11]=0).