文档介绍：数据结构实验报告
评分
满分——5分
学号:2014111962 姓名:施永邦专业:计算机科学与技术
知识范畴:串完成日期:2016年04月6日
实验题目:基于改进型KMP算法的字符串查找与替换
实验内容及要求:
从键盘输入三个字符串s、a、b,在串s中查找子串a,并将串s中的所有a替换为b,输出替换以后的串。注意:a和b的串长不要求相等;若s中无子串a,输出结果与串s相同。
实验目的:掌握字符串模式匹配的KMP算法。
数据结构设计简要描述:
用char型数组储存串s,a,b。用int型数组储存模式串a的next数组。
算法设计简要描述:
在串s中查找子串a的起始位置使用了KMP算法。利用get_nextval函数得到模式串a的nextval数组。函数replace替换s中的a。用指向s的指针p先指向s起始地址,利用KMP算法得到s中第一个a起始位置,然后用b替换a,替换后p指向第一个a起始位置再向后b的长度,查找第二个a的起始位置,依次类推。
输入/输出设计简要描述:
按照提示:先输入s串,然后输入a串。
如果未找到a,则原样输出s。
如果找到第一个a,输出第一个a的位置,并提示输入b,然后会替换剩下的所有a,输出替换后的s,并输出替换次数。
编程语言说明:
使用Visual C++编程。主要代码采用C语言实现;动态存储分配采用C++的new和delete操作符实现;输入与输出采用C++的cin和cout流;程序注释采用C/C++规范。
主要函数说明:
void get_nextval(char *t, int nextval[]); //get_nextval函数
int index_kmp(char *s, char *t, int next[]); //KMP算法
void replace(char *s, char *b, int position, int lena);//替换字符串函数:
//b的长度大于a的情况下先将s中a后边的所有字符向后挪动lenb-lena个位置
//b的长度小于a的情况下先将s中a后边的所有字符向前挪动lena-lenb个位置
//然后将a的字符逐个用b中的字符替换
程序测试简要报告:
无a测试
程序输入输出
结论
程序输出结果与期望输出结果相符。
a、b等长度测试
程序输入输出

结论
程序输出结果与期望输出结果相符。
a、b不等长度测试
程序输入输出

结论
程序输出结果与期望输出结果相符。
源程序代码:
#include <iostream>
#include <iomanip>
using namespace std;
void get_nextval(char *t, int nextval[]) {//get_nextval函数
int j = 1, k = -1;
nextval[0] = -1;
while (t[j]) {
if (k == -1 || t[j - 1] == t[k])
if (t[++k] == t[j])
nextval[j++] = nextval[k];
else nextval[j++] = k;
else k = nextval