文学研究助手与KMP

《文学研究助手与KMP》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、目录一、系统开发的背景2二、系统分析与设计2（一）系统功能要求2（二）系统模块结构设计2三、系统的设计与实现3（一）文档读入3（二）模式匹配KMP3（三）统计并输出3四、系统测试3（-）文档读入31）测试程序：3（二）模式匹配KMP41）测试程序：42）测试结果：5（三）统计并输出51）测试程序52）测试结果：5五、总结6六、附件6（一）程序：6（二）试验结果：9文学研究助手与KMP一、系统开发的背景在读书的过程中，有时会需要去统计一些字符出现的次数以及位置,然而一个一个去数是很不切实际的做法。为方便文学研究人员统计英文小说中某些词的出现次数和位置。所以我设计了一个程序去快捷地实现

2、这一目标。二、系统分析与设计（一）系统功能要求1）英文小说存于一个文木文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在的行的行号，格式口行设计。待统计的“单词”在文木串屮不跨行出现，它或者从行首开始，或者前置以一•个空格符。2）模式匹配要基于KMP算法。3）推广到更一般的模式集匹配问题，并设待查模式串可以跨行（捉示：定义操作GetAChar）o（二）系统模块结构设计通过对题冃的分析，这个程序由以下几部分构成:文学研究助手模式匹配KMP统计模块三、系统的设计与实现（一）文档读入这个模块主要负责从文木文

3、档中读取数据，以便于对文章的编辑。（二）模式匹配KMP这个模块主要负责在文档屮寻找匹配串并记录所在位置。（三）统计并输出!1!系统测试(一)文档读入1)测试程序：while((!feof(fp))){fgets(&s[l],50,fp);s[O]=strlen(s+l);}2)测试结果：反档该入成如希岀灵档:.Muchmeaningcanbeconueyed,clearly,withourelyes,soitisoftensaidthateyescanspeak.Doyouhavesuchkindofexperience?Inabusyounaylookatstranger,but

4、nottoolong・Pressanykeytocontinue—(二)模式匹配KMP1)测试程序：voidGetNext(chart[],intnext[]){intij;i=l；j=0;next[l]=0;while(i

5、

6、t[i]==tU]){i++；j++；next[i]=j;}elsej=next[j];}}intKMP(char*s,char*t,intpos,intnext[]){intij;i=pos;j=l；while(i<=s[0]&&j<=t[O])if(j==O

7、

8、s[i]==t[j]){i++；j++；}elsej=next[j

9、];if(j>t[O])returni-j+1;elsereturn0;}voidmain(){FILE*fp;chars[MAXSIZE],t[MAXSIZE];intflag,next[MAXSIZE];printf(•输入要查询的主串门;scanf(”％s”,&s+l);printf(”输入匹配串:“);scanf(“％s”,t+l);s[O]=strlen(s+l);t[O]=strlen(t+l);GetNext(t,next);flag=KMP(s,t,l,next);if(flag==O)printf(“主串不含有匹配串的内容!“);elseprin廿(“第％d列

10、是所查找内容H,flag);}2)测试结果：输入要查询的主串:abcdefghijklnnopq拿8列皇所查找内容Pressanykeytocontinue—（三）统计并输出1)测试程序GetNext(t,next);fgets(&s[l],50,fp);s[O]=strlen(s+l);q=KMP(s,t/pos,next);if(q==O)hang++;else{if(s[q+t[O]]==''&&s[q-l]==''){printf「第％d行，第％d列是rT,hang,q);printf("%s,,/s+l);hang++;num++;}}2)测试结果:娶查询的壬符

11、串个数3總A匹配串:ifforelse執行，第46列是naylookatstranger,,butnottoolong.Andifh第8行，第19列是anddown,,toseeifthereisanythingwrongv/ith第25行，第咧是ing.asifhetriestodoninateyou，youwillfee辻岀现了3次第6行，第46列是Thesameindailylife.Ifyouarelookedatfor第15行.第丄5列是esatawoman