文学研究助手与模式匹配算法KMP.doc

文档介绍：目录
一、系统开发的背景 1
二、系统分析与设计 1
(一)系统功能要求 1
(二)系统模块结构设计 1
三、系统的设计与实现 2
(一) 运用get_next()函数: 2
(二) 运用Index_KMP()函数: 4
(三) 运用find()查找函数: 5
(四) 调用int main()主函数: 6
四、系统测试 8
(一) 测试int main()函数 8
(二) 测试find()函数: 9
五、总结 10
六、附件(代码、部分图表) 11
文学研究助手与模式匹配算法KMP
一、系统开发的背景
文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置,从而能够更好的查出我们所需要的单词。文学研究助手与模式匹配算法KMP的主要核心就是利用模式匹配算法KMP对该系统进行编程。
二、系统分析与设计
(一)系统功能要求
1、英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕,即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在的行的行号,格式自行设计。待统计的“单词”在文本串中不跨行出现,它或者从行首开始,或者前置以一个空格符。
2、模式匹配要基于KMP算法。
3、推广到更一般的模式集匹配问题,并设待查模式串可以跨行(提示:定义操作GetAChar)。
(二)系统模块结构设计
通过对系统功能的分析,文学研究助手与模式匹配算法KMP。
功能如图1所示。



文学研究助手与模式匹配算法KMP
调用
main()函数
调用
Find()函数
运用
Index
()
函数
运用
Get_
Next()
函数

图1文学研究助手与模式匹配算法KMP系统功能图
通过上图的功能分析,把整个系统划分为4个模块:
运用get_next()函数,该模块主要实现:求模式串T中的next函数值并存入数组next;
运用Index_KMP()函数,该模块主要实现:利用模式串中T的next函数求T在主串S中第pos个字符之后的位置
运用find()查找函数,该模块主要实现:对于输入要查找的每个关键字,调用get_next()函数求模式串中每个关键字所对应的next值,调用KMP模式匹配算法,统计关键字在该行出现的位置;
调用主函数main(),该模块主要实现:输入以创建好的文本文件的路径以及要查找的单词,运用while和if条件语句实现系统的功能。
三、系统的设计与实现
运用get_next()函数:
分析:get_next()函数这一模块主要是求模式串T中next函数值并存入数组next,运用while和if条件语句实现这一模块的功能。
该模块的流程图如图2所示:
开始
Next[j]=k
t[j]!=t[k]
J++;k++
K==0IIt[k]=t[j]
J<t[0]
N
Y
N
K=next[k]
Y
N
结束
next[j]=next[k]

图2
该模块的具体代码如下所示。
void get_next(char T[],int next[]) //求模式串T的next函数值并存入数组next
{
int j=1,k=0;
next[1]=0;
while (j<T[0])
{
if (k==0 || T[k]==T[j])
{
j++;
k++;
if (T[j]!=T[k])
next[j]=k;
else
next[j]=next[k];
}
else
k=next[k];
}
}
运用Index_KMP()函数:
该模块的流程图如图3所示:
开始



i<=s[0]&&j<=T[0]
N

Y
J==0IIs[i]==t[j]
N

Y
j=next[j]
i++;j++;
Y

j>t[0]
N

Y
return i-j+1
return 0
Y
结束
图3
该模块的具体代码如下所示。
int Index_KMP(char *S,char *T,int pos)
{ // 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法
int 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;