KMP专题

KMP专题

KMP算法说明及理解

  • 引入跳转表next[ ],利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的
  • 什么是next[ ]?看完下面构造next[]的图解后便可明白
  • 朴素算法复杂度为 O(nm)
  • 通过一个 O(m) 的预处理,使匹配的复杂度降为 O(n+m)
  • 应用:模式串A是否在原串B中出现,出现几次,第一次出现的位置…等等

图解

“造诣不够,后续再补”

代码编写:

  • 变量定义

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    /*
    s : 原串
    e : 模式串
    Next : 模式串的next数组
    n : s的长度
    m : e的长度
    */
    const int maxn = 1e6+7;
    const int maxx = 1e4+7;
    int s[maxn], e[maxx];
    int Next[maxn], n, m;
  • 模式串next数组构造

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    void getNext(){ //此为求解模式串e的next数组
    int j, k;
    j = 0, k=-1;
    Next[0] = -1;
    while(j < m){
    if(k == -1 || e[j] == e[k]){
    Next[++j] = ++k;
    } else {
    k = Next[k];
    }
    }
    return ;
    }
    // 应用:getNext()
  • 查询模式串在原串中第一次出现的下标,从0开始

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int KMP_INDEX(){
    int i = 0, j = 0;
    while(i < n && j<m){
    if( j == -1 || s[i] == e[j]){
    i++, j++;
    } else {
    j = Next[j];
    }
    }
    if(j == m) return i-m;
    else return -2;
    }
    // 应用:求解模式串next数组后,调用 KMP_INDEX()
  • 查询模式串在原串中出现的次数(可重叠,如aaaa,aa出现3次)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    int KMP_CNT()
    {
    int ans = 0;
    int i, j = 0;
    for(i = 0; i < n; i++) {
    while(j > 0 && s[i] != e[j]) j = Next[j];
    if(s[i] == e[j]) j++;
    if(j == m) {
    ans++;
    j = Next[j];
    /*
    若要不可重叠的,
    将j = Next[j] 改为 j = 0;
    如: aaaa,aa出现 2 次
    */
    }
    }
    return ans;
    }
  • 求循环节长度

    1
    2
    3
    4
    5
    6
    7
    8
    getNext(); //求解next数组
    int ans = m - Next[m];
    if(ans != m && m%ans == 0){ //若满足此条件说明,模式串存在循环节
    printf("%d\n", 0);
    } else{
    printf("%d\n", ans-Next[m]%ans);
    //求解需要增加几个字母能使得模式串构成循环节
    }