串的模式匹配算法之KMP与BF

这几天做手机软件, 都不怎么看一些算法小程序了, 同学数据结构作业,急需交,帮其做

/**/ /*
* 文件名:KMP_BF.cpp
* 描述:实验内容:
*       比较BF算法和KMP算法的优劣
*       实验基本要求:
*      1.采用定长顺序显示表示串长的结构来存储串(结构定义见课件第17张幻灯片)
*
*      2.实现BF算法(即朴素算法),BF函数头如下:(参见课件第34张幻灯片)
*        int Index_BF(SString S, SString T) {}// 返回子串T在主串S中第0个字符之后的位置。若不存在，返回-1
*
*       3.实现getnext函数和kmp算法函数,参见课件第58和第53张幻灯片,函数头分别如下：
*         int Index_KMP(SString S, SString T){}//功能同Index_BF 
*         void get_next(SString T, int &next[]){}
*
*       4,编写主函数，分别定义SSsting类型的两个变量，并通过键盘输入串值，并为串设置串长，并分别验证两种匹配算法。
*
*        实验附加要求：
*        修改以上的两种算法函数，使之可以统计字符的比较次数，并最终输出类似以下信息：
*        主串长？？，模式串长？？
*        BF算法，比较次数为？？
*        KMP算法，比较次数为？？其中求next值比较的次数为？？
*        实验提交要求：
*        实验完成后，提交程序源文件（请务必以学号命名）和包含程序源文件及实验运行结果屏幕截图的word文档（也请务必以学号命名）。  
*创建时间:2007-11-7
*/

#include < stdio.h >
#include < stdlib.h >

#define  maxstrlen    256

int  count_BF;
int  count_KMP;
int  count_next;

//  1,采用定长顺序显示表示串长的结构来存储串(结构定义见课件第17张幻灯片)
typedef  struct
... {
    char ch[maxstrlen];
    int length;
}  sstring;

//  2,实现BF算法(即朴素算法)
int  Index_BF(sstring S, sstring T)
... {
    int i, j, p;
    
    for(i = 0; i < S.length - T.length + 1; i++)
    ...{
        p = i;
        for(j = 0; j < T.length; j++)
        ...{
            // 假如不等,跳出循环
            count_BF++;
            if(S.ch[p] != T.ch[j])
                break;
            else
                p++;
        }
        if(j == T.length)
            break;
    }

    return (j == T.length) ? (p - j) : -1;
}

// 实现getnext函数和kmp算法函数
void  get_next(sstring T,  int   * next)
... {
    int i, j;

    j = -1;
    next[0] = -1;
    i = 0; 
    while(i < T.length - 1)
    ...{
        if(j == -1 || T.ch[i] == T.ch[j])
        ...{
            j++;
            i++;
            next[i] = j;
        }
        else
            j = next[j];

        count_next++;
    }
}

int  Index_KMP(sstring S, sstring T) // 功能同Index_BF 
... {
    int i, j;
    int next[maxstrlen];

    get_next(T, next);

    i = 0;
    j = 0;
    while(i < S.length && j < T.length)
    ...{
        if(j == -1 || S.ch[i] == T.ch[j])
        ...{
            j++;
            i++;
        }
        else
            j = next[j];

        count_KMP++;
    }

    return (j == T.length) ? (i - j) : -1;
}

int  main()
... {
    sstring S, T;
    char ch;
    int v_BF, v_KMP;
    
    S.length = 0;
    T.length = 0;
    printf("请输入主串 S : ");
       while((ch = getchar()) != '/n')
              T.ch[T.length++] = ch;
      T.ch[T.length] = '/0';

       v_BF = Index_BF(S, T);
       v_KMP = Index_KMP(S, T);

      printf("主串为 ==> %s /t| 模式串为 ==> %s/n", S.ch, T.ch);
      printf("主串长 ==> %d /t| 模式串长 ==> %d/n", S.length, T.length);
      printf("BF算法,返回值为 ==> %d /t 比较次数为 ==> %d/n",v_BF, count_BF);
      printf("KMP算法,返回值为 ==> %d    比较次数为 ==> %d    求next值的比较次数为 ==> %d/n", v_KMP, count_KMP, count_next);

      return 0;
}

 在测试程序时发现一个问题:

最后两个printf

 printf("BF算法,返回值为 ==> %d /t 比较次数为 ==> %d/n",v_BF, count_BF);
 printf("KMP算法,返回值为 ==> %d    比较次数为 ==> %d    求next值的比较次数为 ==> %d/n", v_KMP, count_KMP, count_next);

之前写成这样的:

 printf("BF算法,返回值为 ==> %d /t 比较次数为 ==> %d/n",Index_BF(S, T), count_BF);
 printf("KMP算法,返回值为 ==> %d    比较次数为 ==> %d    求next值的比较次数为 ==> %d/n", Index_KMP(S, T), count_KMP, count_next);

发现输出的count_BF,count_KMP,count_next值总是0;后来改在printf前面调用Index_BF(),Index_KMP()两个函数; 三个count 值才能正常输出.