大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > 字符串算法——KMP算法

字符串算法——KMP算法

关键词:字符串算法KMP字符串算法——KMP算法  阅读(676) 赞(11)

[摘要]本文主要是对字符串算法——KMP算法的讲解,希望对大家学习字符串算法——KMP算法有所帮助。

  KMP算法是对字符串匹配算法的一个重大改进 , 创造性的利用子串本身的特性 , 来改进算法的效率。

  KMP算法的关键或则精华 , 就是在与 next[ ] 的计算。

  假设存在主串 S 和 子串 T , 我们在某一趟匹配中 , 发现 T(k) != S(i+1)

  那我们就得到了一个部分的匹配结果

  即:T(1)……T(k-1) = S(i-k+1) …… S(i-1)

  我们假设存在一个 j < k 使得: T(1)……T(j-1) = S(i-k+1)……S(i-k+j-1)

  也就是说 T(1)……T(j-1) = T(k-j)……T(k-1)

  所以这时我们就需要把子串向右移动 k-j 位 , 而如果 此时不存在这样的情况 , 也就是 j = 0 , 那么我们就需要向右移动 k 位

  因此我们只需要求出子串中每个位置对应的 j 既可

  这就是KMP算法的思想

  因此next() 函数的定义如下:

  0 j = 1 时

  next()= max( k / 1<=k

  1 当不存在上面的K且T(1) != T(j)

  0 当不存在上面的K且T(1) != T(i)

  求next() 函数的代码如下:

  char s[100]; //被匹配字符串

  char t[100]; //匹配字符串

  int next[100];  //存储匹配串中每个字符应移的距离

  int s_length , t_length;//被匹配串和匹配串的字符长度

  void getnext()

  {

  int i = 0, j =-1;

  next[i] = -1;

  while(i < t_length)

  {

  while(j >= 0 && t[i] != t[j])  j = next[j]; //和该字符前面的字符比较 , 看是否和前面的字符相同

  i++;  j++;

  if(t[i] == t[j])  next[i] = next[j];//如果当前两字符相同 ,

  else next[i] = j;

  }

  for(i = 0; i < t_length; i++)

  printf("%d\n" , next[i]);

  }

  //向右滑动的距离为:j-next[j]



相关评论