BF与KMP算法

BF(朴素算法)

BF.c(字符数组从0开始)

• Index_BF函数

  int Index_BF(char * a, char * b)
  {
      int i=0, j=0;
  
      // 遍历两个字符串，都不为空继续执行
      while( *(a+i) && *(b+j) )
      {
          // 如果对应字符相等，继续执行
          if(*(a+i) == *(b+j))    {i++; j++;}
          // 否则i后移一位，j回到头位置
          else{i=i-j+1; j=0;}
      }
      // 如果*(b+j)=='\0',则在a中有b，返回第一次出现的位置
      if(!*(b+j)) return i-j+1;
      // 否则返回-1
      else return -1;
  }

• 主函数main

  #include<stdio.h>
  
  // 若b字符串在a中，返回b第一次出现的次序
  int Index_BF(char * a, char * b);
  
  int main(void)
  {
      char *a = "I know, sgy is handsome!";
      char *b = "sgy";
  
      int loc = Index_BF(a, b);
  
      printf("%d\n",loc);
      return 0;
  }

• 输出

  9

KMP算法

难点——求next数组

• 求next数组

  void getNext(Str substr, int next[])
  {
      int j = 1, t = 0;
      next[1] = 0;
      while(j < substr.length)
      {
          if(t == 0 || substr.ch[j] == substr.ch[t])
          {
              next[j+1] = t+1;
              ++t;
              ++j;
          }
          else
              t = next[t];
      }
  }

优化——求nextval数组

• 求nextval数组

  void getNextval(Str substr, int nextval[])
  {
      int j = 1, t = 0;
      nextval[1] = 0;
      while(j < substr.length)
      {
          if(t==0 || substr.ch[j] == substr.ch[t])
          {
              if(substr.ch[j+1] != substr.ch[t+1])
                  nextval[j+1] = t + 1;
              else
                  nextval[j+1] = nextval[t+1];
              ++j; ++t;
          }
          else
              t = nextval[t];
      }
  }

实现——测试

• KMP函数

  int KMP(Str str, Str substr, int nextval[])
  {
      int i = 1, j = 1;
      while(i <= str.length && j <= substr.length)
      {
          if(j == 0 || str.ch[i] == substr.ch[j])
          {
              ++i;
              ++j;
          }
          else
              j = nextval[j];
      }
      if(j > substr.length)
          return i - substr.length;
      else
          return 0;
  }

• 主函数main

  #include<stdio.h>
  #include "string.h"
  
  int KMP(Str str, Str substr, int nextval[]);
  void getNext(Str substr, int next[]);
  void getNextval(Str substr, int nextval[]);
  
  // 本例都是下标从1开始存储
  int main(void)
  {
      char *a = " I know, sgy is handsome!";
      char *b = " sgy";
      Str str, substr;
  
      if(1 == strAssign(&str, a) && 1 == strAssign(&substr, b))
      {
          int nextval[substr.length];
          getNextval(substr, nextval);
          int i = 0;
          int loc = KMP(str, substr, nextval);
          printf("location = %d\n", loc);
      }
  
      return 0;
  }

• 输出

  location = 9