[终于有感觉了]字符串匹配的KMP算法

时间：2010-10-08 来源：鲁斯特&hope

Matrix67大牛写的非常生动，推荐大家看看他的。

以下是连接：http://www.matrix67.com/blog/archives/115

我要说的是Matirx67大牛没有提到的预处理数组的再度优化。

对于当前假设A串到了i，B串到了j，然而A[i+1]≠B[j+1]，那么j变成f[j],但是如果B[f[j]+1]依旧不等于A[i+1]，那么我们还要继续找。但是这个我们可以预处理出来，经过这个处理，去除了很多匹配中的无效对比，速度增快。详见下面的Ff函数。

//将B串和A串进行多次匹配并输出匹配成功位置 
//by Sephiroth Lee
//date: 10/8/2010
#include <stdio.h>
#include <string.h>
#define MAXN 100010 //最大长度
char A[MAXN],B[MAXN]; 
int f[MAXN],n,m,tot;
void Init() {//读入数据 
  scanf("%s%s",A,B);
  n = strlen(A);
  m = strlen(B);
  memmove(A + 1,A,sizeof(char)*n);
  memmove(B + 1,B,sizeof(char)*m);
}
void Init_f() {//初步预处理 
  int k=0;
  for (int i = 2;i <= m;++i) {
    while ((k > 0) && (B[k + 1] != B[i]))
      k = f[k];
    if (B[k + 1] == B[i])
      ++k;
    f[i] = k;
  }
}
void Ff() {//f数组优化 
  Init_f();
  int k;
  for (int i = 1;i <= m;++i) {
    k = f[i];
    while ((k > 0) && (B[k + 1] == B[i + 1]))
      k = f[k];
    f[i] = k;
  }
}
void Solve() {//进行匹配
  Ff();
  int k = 0;
  for (int i = 1;i <= n;++i) {
    while ((k > 0) && (B[k + 1] != A[i]))
      k = f[k];
    if (B[k + 1] == A[i])
      ++k;
    if (k == m) {
      ++tot;
      printf("%d\n",i-m+1);
    }
  }
  printf("%d\n",tot);
}
int main() {//主函数 
  freopen("sample.in","r",stdin);
  freopen("sample.out","w",stdout);
  Init();
  Solve();
  return 0;
}

相关阅读更多 +