数据结构 基于BF和KMP的串模式匹配算法设计与实现.doc

实验：基于BF和KMP的串模式匹配算法设计与实现（1）BF算法 Demo4_1(BF).exe实验源程序代码：/ Demo_4.cpp : Defines the entry point for the console application./#include stdafx.h#include#include#include#define MaxSize 100/串的存储表示 typedef structchar strMaxSize;String;/BF的串模式匹配算法设计与实现 int BFIndex(String S, int pos, String T)int i = pos; intj = 0;while(i =strlen(S.str)& j=strlen(T.str)if(S.stri-1 = T.strj)/数组下标从0开始 i+; j+;elsei = i-j+1; j = 0; if (j=strlen(T.str) return (i-strlen(T.str); else return 0;int main(int argc, char* argv)String a,b;int c,d;printf(请输入主串A的字符:);scanf(%s,a.str); printf(请输入子串B的字符:);scanf(%s,b.str);printf(请输入pos的值:);scanf(%d,&c); d=BFIndex(a,c,b);/调用BFIndex函数printf(子串B在主串A中第pos个字符之后的位置为:);printf(%dn,d); system(pause);return 0;（2） KMP算法 Demo_4_2（KMP）.exe实验源程序代码：/ 实验4KMP算法.cpp : Defines the entry point for the console application./#include stdafx.h#include#include#include#define MaxSize 100/串的存储表示 typedef structchar strMaxSize+1;/0号单元存放串的长度String;/next的算法实现void GetNext(String T, int next)int i= 1, j=0; next1 =0; while(iT.str0)if(j=0|T.stri=T.strj) +i;+j;nexti=j; else j=nextj; /KMP的串模式匹配算法设计与实现 int KMPIndex(String S, int pos, String T,int next)int i = pos, j =1;while(i=S.str0& j=T.str0)if(j=0|S.stri = T.strj) i+; j+;elsej=nextj; if (j=T.str0)return (i-T.str0); else return 0;int main(int argc, char* argv)String a,b;int c,d; int next100;printf(请输入主串A的字符:);scanf(%s,a.str); printf(请输入子串B的字符:);scanf(%s,b.str);printf(请输入pos的值:);scanf(%d,&c);GetNext(b,next); d=KMPIndex(a,c,b,next);/调用KMP