KMP代码

  1. KMP匹配

    1. // KMP搜索：下标0处存长度
    2. int KMP(char *str, char *substr, int next[]) {
    3.  int i=1,j=1;
    4.  while (i<=str[0] && j<=substr[0]) {
    5.      if (j==0 || str[i]==substr[j]) {
    6.          ++i;++j;
    7.      } else {
    8.          j = next[j]; //失配，回溯
    9.      }
    10.  }
    11.  if (j>substr[0])  return i-substr[0]; //匹配成功
    12.  else: return 0; //匹配失败
    13. }

  2. 求next数组

    // T[0]存着字符串长度
void getnext(char *T, int next[]) {
 int j=1,t=0;
 next[1] = 0; //特殊状态
 while (j<T[0]) { //已知next[j]求next[j+1]，所以j不能等于T[0]
     if (t==0 || T[j]==T[t]) {
         next[j+1] = t+1;
         ++j;++t;
     }
     else t = next[t];
 }
}

  3. 求nextval数组

【第一种】在求next数组的算法中修改部分逻辑，即可求nextval数组

// 在求next数组的过程中，求nextval数组
void getnextval(char *T, int next[], int nextval[]) {
    int j=1, t=0;
    next[1] = 0;
    nextval[1]=0; //特殊情况
    while (j<T[0]) { //已知next[j]，求得next[j+1] --> 再依据next[j+1]，求得nextval[j+1]
        if (t==0 || T[j]==T[t]) { //匹配成功
            next[j+1] = t+1; //求得next[j+1]
            // 求nextval[j+1]
            if ( T[j+1] != T[ next[j+1] ] ) nextval[j+1] = next[j+1];
            else nextval[j+1] = nextval[ next[j+1] ];
            ++j;++t;
        }
        else t = nextval[t];
    }
}

【第二种】由模式串直接求得nextval数组

// 由模式串T求nextval数组
void getnextval(char *T, int nextval[]) {
    int j=1, t=0;
    nextval[1] = 0; //初始情况
    while (j < T[0]) { //已知nextval[j]，求next[j+1]
        if (t==0 || T[j]==T[t]) {
            if (T[j+1]!=T[t+1]) nextval[j+1] = t+1;
            else nextval[j+1] = nextval[t+1];
            ++j; ++t;
        }
        else t = nextval[t];
    }
}

KMP手算

【例题】模式串”ababaaababaa”，求nextval数组（下标从1开始，0记录长度）
【先求next数组】

  1. 先画出表格（下标、T、next），并赋值特殊情况next[1]=0
  2. 看下标j那列，记下前面的子串T[1]-T[j-1]，找出最长的前后缀
    1. 没有相同的前后缀 —> next[j] = 1
    2. 有相同的前后缀 —> 取最长的前后缀，长度为len —> next[j]=len+1

【再求nextval数组】

  1. 画出nextval行，并赋值特殊情况nextval[1]=0
  2. 【算法：求单元格(j, nextval)】先锁定下标为j的那一列 —> 然后看第j列，next那一行（j, next）的值t —> 然后看第t列，T那一行（t, T）—> 用(t, T)和(j, T)比较
    1. (t, T)==(j, T) 的话：(j, nextval)=(t, nextval)
    2. (t, T)≠(j, T)的话：(j, nextval)=(j, next)
  3. 【举例：求单元格(5,nextval)】锁定下标为5的那一列 —> (5, next)=3 —> (3, T)=a —> (3, T)=a与(5, T)=a比较 —> 相同，则(5, nextval)=(3, nextval)=3
  4. 【举例：求单元格(6, nextval)】锁定下标为6的那一列 —> (6, next)=4 —> (4, T)=b —> (4, T)=b与(6, T)=a比较 —> 不同，则(6, nextval)=(6, next) | 下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | —- | | T | a | b | a | b | a | a | a | b | a | b | a | a | | next | 0 | 1 | 1 | 2 | 3 | 4 | 2 | 2 | 3 | 4 | 5 | 6 | | nextval | 0 | 1 | 0 | 1 | 0 | 4 | 2 | 1 | 0 | 1 | 0 | 4 |

【链接】KMP全盘复习