bm算法-C语言实现.docx

bm算法,C语言实现bm算法,C语言实现bm算法,C语言实现PAGE#bm算法,C语言实现编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（bm算法,C语言实现）的内容能够给您的工作和学习带来便利。同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快业绩进步，以下为bm算法,C语言实现的全部内容。算法设计与分析基础实验报告实验名称BM算法的实现学院计算机学院专业班级计算机科学与技术09(2)班学号3109005933姓名黄进杰指导教师顾国生2012年12月03日实验目的与要求理解Boyer—Moore算法的思想掌握用Boyer-Moore算法来查找字符或字符串的方法实验内容＃include〈stdio.h>#include<string.h〉＃include〈stdlib.h〉#defineTMax10000//文本串最大值＃definePMax200//模式串最大值/*函数：int＊MakeSkip(char＊,int)目的：根据坏字符规则做预处理，建立一张坏字符表参数：ptrn=>模式串PPLen=>模式串P长度返回：int*-坏字符表*/int＊MakeSkip(char*ptrn,intpLen）｛inti;//为建立坏字符表，申请256个int的空间/*PS:之所以要申请256个，是因为一个字符是8位，所以字符可能有2的8次方即256种不同情况＊/int*skip=(int＊）malloc(256＊sizeof（int)）;if（skip==NULL）｛fprintf(stderr,”mallocfailed!"）;return0;｝//初始化坏字符表,256个单元全部初始化为pLenfor（i=0;i<256;i++)｛*（skip+i)=pLen;｝//给表中需要赋值的单元赋值，不在模式串中出现的字符就不用再赋值了while(pLen！=0)｛＊(skip+(unsignedchar)＊ptrn++)=pLen--；}returnskip；}/＊函数:int*MakeShift（char＊,int)目的：根据好后缀规则做预处理,建立一张好后缀表参数：ptrn=>模式串PPLen=>模式串P长度返回：int*—好后缀表*/int*MakeShift（char*ptrn，intpLen){//为好后缀表申请pLen个int的空间int*shift=(int*)malloc（pLen＊sizeof（int))；int＊sptr=shift+pLen-1；//方便给好后缀表进行赋值的指标char*pptr=ptrn+pLen-1;//记录好后缀表边界位置的指标charc；if(shift==NULL){fprintf(stderr,”mallocfailed!”）；return0;｝c=*（ptrn+pLen-1）；//保存模式串中最后一个字符,因为要反复用到它＊sptr=1;//以最后一个字符为边界时,确定移动1的距离pptr——;//边界移动到倒数第二个字符（这句是我自己加上去的，因为我总觉得不加上去会有BUG，大家试试“abcdd”的情况,即末尾两位重复的情况）while（sptr--!=shift）//该最外层循环完成给好后缀表中每一个单元进行赋值的工作｛char＊p1=ptrn+pLen-2，*p2,＊p3；//该do.。。while循环完成以当前pptr所指的字符为边界时，要移动的距离do｛while(p1>=ptrn&&*p1--！=c）;//该空循环，寻找与最后一个字符c匹配的字符所指向的位置p2=ptrn+pLen—2；p3=p1；while（p3〉=ptrn&&*p3——==＊p2—-＆&p2〉=pptr）;//该空循环，判断在边界内字符匹配到了什么位置}while（p3〉=ptrn&＆p2>=pptr）;＊sptr=shift+pLen-sptr+p2-p3;//保存好后缀表中,以pptr所在字符为边界时，要移动的位置/*PS：在这里我要声明一句，*sptr=（shift+pLen—sptr)+p2-p3;大家看被我用括号括起来的部分，如果只需要计算字符串移动的距离，那么括号中的那部分是不需要的.因为在字符串自左向右做匹配的时候，指标是一直向左移的，这里＊sptr保存的内容,实际是指标要移动距离，而不是字符串移动的距离.我想SNORT是出于性能上的考虑，才这么做的。*/pptr—-；//边界继续向前移动}returnshift；}/＊函数：int＊BMSearch（c