avatar

BF与KMP算法

BF(朴素算法)

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

  • Index_BF函数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    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
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    #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;
    }
  • 输出
    1
    9

KMP算法

难点——求next数组

  • 求next数组
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    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数组
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    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函数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    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
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    #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;
    }
  • 输出
    1
    location = 9
文章作者: Gy
文章链接: http://sgyat.cn/2020/04/12/KMP算法/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 年轻没有梦
打赏
  • 微信
    微信
  • 支付宝
    支付宝

评论