數(shù)據(jù)結(jié)構(gòu)-基于BF和KMP的串模式匹配算法設(shè)計(jì)與實(shí)現(xiàn)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上實(shí)驗(yàn)：基于BF和KMP的串模式匹配算法設(shè)計(jì)與實(shí)現(xiàn)（1）BF算法 實(shí)驗(yàn)源程序代碼：/ 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/串的存儲(chǔ)表示 typedef structchar strMaxSize;String;/BF的串模式匹配算法設(shè)計(jì)與實(shí)

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ù)組下標(biāo)從0開(kāi)始 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、;請(qǐng)輸入主串A的字符:");scanf("%s",a.str); printf("請(qǐng)輸入子串B的字符:");scanf("%s",b.str);printf("請(qǐng)輸入pos的值:");scanf("%d",&c); d=BFIndex(a,c,b);/調(diào)用BFIndex函數(shù)printf("子串B在主串A中第pos個(gè)字符之后的位置為:");printf("%dn",d); system("pause");return 0

4、;（2） KMP算法 實(shí)驗(yàn)源程序代碼：/ 實(shí)驗(yàn)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/串的存儲(chǔ)表示 typedef structchar strMaxSize+1;/0號(hào)單元存放串的長(zhǎng)度String;/next的算法實(shí)現(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的串模式匹配算法設(shè)計(jì)與實(shí)現(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("請(qǐng)輸入主串A的字符:");scanf("%s",a.str); printf("請(qǐng)輸入子串B的字符:");scanf("%s",b.str);printf("請(qǐng)輸入pos的值:");scanf("%d",&c);GetNext(b,next); d=KMPIndex(a,c,b,next);/調(diào)用KMPIndex函數(shù)printf("子串T在主