數(shù)據(jù)結構-基于BF和KMP的串模式匹配算法設計與實現(xiàn)

1、精選優(yōu)質文檔-傾情為你奉上實驗：基于BF和KMP的串模式匹配算法設計與實現(xiàn)（1）BF算法 實驗源程序代碼：/ Demo_4.cpp : Defines the entry point for the console application./#include "stdafx.h"#include<stdio.h>#include<string.h>#include<stdlib.h>#define MaxSize 100/串的存儲表示 typedef structchar strMaxSize;String;/BF的串模式匹配算法設計與實

2、現(xiàn) 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)/數(shù)組下標從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("

3、;請輸入主串A的字符:");scanf("%s",a.str); printf("請輸入子串B的字符:");scanf("%s",b.str);printf("請輸入pos的值:");scanf("%d",&c); d=BFIndex(a,c,b);/調用BFIndex函數(shù)printf("子串B在主串A中第pos個字符之后的位置為:");printf("%dn",d); system("pause");return 0

4、;（2） KMP算法 實驗源程序代碼：/ 實驗4KMP算法.cpp : Defines the entry point for the console application./#include "stdafx.h"#include<stdio.h>#include<string.h>#include<stdlib.h>#define MaxSize 100/串的存儲表示 typedef structchar strMaxSize+1;/0號單元存放串的長度String;/next的算法實現(xiàn)void GetNext(String T, i

5、nt next)int i= 1, j=0; next1 =0; while(i<T.str0)if(j=0|T.stri=T.strj) +i;+j;nexti=j; else j=nextj; /KMP的串模式匹配算法設計與實現(xiàn) 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.s

6、tr0); 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);/調用KMPIndex函數(shù)printf("子串T在主