文档介绍：目录
一、 系统开发的背景 3
二、 系统分析与设计 3
(一) 系统功能要求 3
(二) 系统模块结构设计 3
三、 系统的设计与实现 4
(一) 文档读入 4
(二) 模式匹配KMP 4
(三) 统计并输出 4
四、 系统测试 4
(一) 文档读入 4
1) 测试程序: 4
(二) 模式匹配KMP 5
1) 测试程序: 5
2) 测试结果: 6
(三) 统计并输出 6
1) 测试程序 6
2) 测试结果: 6
五、 总结 7
六、 附件 7
(一) 程序: 7
(二) 试验结果: 10
文学研究助手与KMP
系统开发的背景
在读书的过程中,有时会需要去统计一些字符出现的次数以及位置,然而一个一个去数是很不切实际的做法。为方便文学研究人员统计英文小说中某些词的出现次数和位置。所以我设计了一个程序去快捷地实现这一目标。
系统分析与设计
系统功能要求
英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕,即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在的行的行号,格式自行设计。待统计的“单词”在文本串中不跨行出现,它或者从行首开始,或者前置以一个空格符。
模式匹配要基于KMP算法。
推广到更一般的模式集匹配问题,并设待查模式串可以跨行(提示:定义操作GetAChar)。
系统模块结构设计
通过对题目的分析,这个程序由以下几部分构成:
文学研究助手
小说文档
模式匹配KMP
统计模块
系统的设计与实现
文档读入
这个模块主要负责从文本文档中读取数据,以便于对文章的编辑。
模式匹配KMP
这个模块主要负责在文档中寻找匹配串并记录所在位置。
统计并输出
系统测试
文档读入
测试程序:
while((!feof(fp)))
{
fgets(&s[1],50,fp);
s[0]=strlen(s+1);
}
测试结果:
模式匹配KMP
测试程序:
void GetNext(char t[],int next[])
{inti,j;
i=1;
j=0;
next[1]=0;
while(i<t[0])
{if(j==0||t[i]==t[j])
{i++;
j++;
next[i]=j;
}
else
j=next[j];
}}
int KMP(char *s,char *t,intpos ,int next[])
{
inti,j;
i=pos;
j=1;
while(i<=s[0]&&j<=t[0])
if(j==0||s[i]==t[j])
{
i++;
j++;
}
else
j=next[j];
if(j>t[0])
return i-j+1;
else
return 0;
}
void main ()
{
FILE *fp;
char s[MAXSIZE],t[MAXSIZE];
intflag,next[MAXSIZE];
printf("输入要查询的主串:");
scanf("%s",&s+1);
printf("输入匹配串:");
scanf("