简单匹配算法和KMP算法
实现字符串匹配的简单匹配算法和ＫＭＰ算法,并且使用相同的比较字符串重复比较至少５000次,计算两者的时间差别实验要求：完成实验内容要求，编写程序实现提交报告，报告分三部分内容：1） 自己是怎么做的？遇到什么问题，怎样解决的?2） 用了哪些数据,得到什么结果？程序结果是不是跟你想的一样？为什么不一样?3） 还有哪些值得改进或者不懂的？一、 实验方案源程序的头文件定义为：＃incｌude 〈stdｉo．h〉＃incluｄe ＜sｔdliｂ.h>＃iｎclｕde
\n”，ｋ）;ﻩｉf（j〉T［0]) ﻩ retｕrn i—T［0]； else retｕrn 0;}／/Ｉndexvoid ｇet＿ｎext（SString T,int ｎｅxt[］）{ //求KMP算法中的neｘｔ函数值，并存入数组next[］ ｉnｔ i=１; nexｔ[１］=0;ﻩ inｔ ｊ=0；ﻩ while（ｉ〈（int）T[0]）ﻩ ｛ﻩﻩ iｆ（j＝=0 ｜｜ T[ｉ］＝=T［ｊ]）ﻩ { ﻩﻩ ＋+i;ﻩ ﻩ ++ｊ； ﻩ iｆ（T［i］!＝T［j］) nexｔ[i]=j; ﻩ ｅlse ｎｅｘｔ［i]=neｘt[ｊ］； ﻩ } else j=neｘt［j］; ｝｝//nｅxtint Index_KMP（ＳStriｎg S,SString T,inｔ poｓ）｛ //KＭP算法的实现过程 ｉｎt nｅｘｔ［MＡXＳTRLEN];ﻩiｎt i=pos； inｔ j=１，k=0；ﻩwhiｌe（ｉ＜＝(ｉnt）Ｓ[0] && j〈＝(iｎt)T[0］）ﻩ｛ ﻩif（ｊ=＝０ || S[i]＝=T［j]） ｛ ﻩﻩ+＋ｉ; ++j；ﻩ ｝ﻩﻩｅlsｅﻩ ｛ﻩ ｇeｔ＿nexｔ（T，ｎeｘt）； ﻩﻩj=nexｔ［j］; ﻩ} k++； } printf（"ＫMP匹配查找的时间复杂度为％d。
\n"，ｋ);ﻩiｆ(ｊ>（int）T［０］)ﻩ retｕrｎ i—Ｔ［0]; else return 0;}/／Indeｘ＿ＫMP源程序中主函数如下：void maiｎ（）｛ SＳtring T，S；ﻩint ｐ，i,j，ｋ1,k2； ｐ=1；ﻩi=1; ｊ=1；ﻩprintf（”请输入字符串匹配主串：\n”）; geｔs（&S［1]);ﻩprintf（＂请输入字符串匹配模式串:\n")；ﻩgets（&Ｔ[1］）； for（i=1；S［i］！=NULL;i++）ﻩ｛ ﻩＳ［0］=（int）(i)； ｝ ｐrintf（"字符串匹配中主串：\n”）； puｔs(&Ｓ［１]）;ﻩfor（ｊ=1;T［j］！=ＮULL；j+＋)ﻩ{ﻩ T[０]＝（ｉｎt)（j)； } ｐrinｔｆ（"＼n字符串匹配中模式串:\n"）;ﻩpｕts（＆T［1]）； ﻩｐrintf(＂-————————-普通算法——-——---————\n”）；ﻩk1=Indｅｘ（S，Ｔ，p）；ﻩprintｆ（”普通匹配算法得模式串位置:%d\n\n"，k1）;ﻩprｉｎtｆ（＂———————---KMP算法———————-——-—\n”)；ﻩk2=Iｎdｅｘ_KMP(S，T，p); pｒintf(＂KMP算法得模式串位置：％d\n＂,k2)；｝二、 实验结果和数据处理（１）程序运行时，输入主串为S=’ｑｑqｑqｑqqqｑqqｑqqqqqqqqqqqqｑｑqqqｑqqｑqqqqqqqqqｑqｑｑqqｑｑqqqqqqqqqqqqqqqqqqqqqqｑqqｑqqqqqqqqqqqqqqqqqqqqqｑqｑｑqｑqqqqqqqqqqqｑｑｑqqｑqqqqｗs ‘；模式串为T='ｑqqqqqqｑqqqqqqqqqqqqqqｑqqqqqqｑqqqqqqqｑqｑqqqｑqqqqqqｑqqｑqqqqqｑqｑqqqqqqqqqqｑqｑqqｑｗs'；运行界面如下:小结：得到普通匹配算法的时间复杂度为3793,而KMP算法的时间复杂度为174，显然在匹配算法中，KMP算法优于普通算法，节省了时间以及资源。
2）当输入主串为S＝’A ＳTＲING SＥARCHING EXAMPLＥ CONSIＳTING OF ＳIＭPLＥ TEＸT'；模式串为T=’STＩNG’运行结果如下:小结：当主串重复出现的字符不多时,ＫＭP算法的优势无法明显体现出来4 / 4。
