1 / 6
数据结构实验报告
知识范畴：字符串 完成日期：2021 年 10 月 20 日
实验题目：基于改进 KMP 算法的字符文件子串查找与替换
课程目标 1（60%）
课程目标 2（40%）
程序代码及测试
写作、排版、代码注释等
得分(100 分)
期末成绩占比 10%
批阅人签字
实验内容及要求：
从键盘输入字符文件名 1、字符文件名 2 以及子串 t1 和 t2。编写程序，将字符文件 1 中
所有 t1 串替换为 t2 串，替换结果输出为文件 2，在屏幕上显示替换总次数。要求子串查找采
用改进 KMP 算法。若文件 1 不包含子串 t1，应显示替换次数为 0 ，且输出的文件 2 应与文件 1
内容完全相同。
实验目的：掌握 KMP 算法。
数据结构设计简要描述：
采用改进 KMP 算法，将 next 改进为 nextval 数组，循环调用 kmp 函数进行子串的查找和
替换。
算法设计简要描述：
通过循环调用 kmp 算法函数来得到匹配成功的初始位置 i-j，然后将 i-j 位置前所有字符
输出到文件 2，再将字串 t2 输出到文件 2，从主串的 i 位置进行下次循环，直到主串读取到最
后一位结束循环，最后将主串中所有剩余字符输出到文件 2。
输入/输出设计简要描述：
从键盘输入字符文件名 1、字符文件名 2 以及子串 t1 和 t2 后从文件 1 中读取主串。
将字符文件 1 中所有 t1 串替换为 t2 串输出在字符文件 2 中。
输入与输出有文字提示。
编程语言说明：
使用 Visual C++编程。 主要代码采用 C 语言实现 ；输入与输出采用 C++的 cin 和 cout
流；程序注释采用 C/C++规范。
主要函数说明：
void get_nextval(char *t, int nextval[]) //求 nextval 数组
int Kmp(char *s, char *t, int next[],int &i) //kmp 算法
程序测试简要报告：
(1) 测试实例 1
资源评论
