基于改进型KMP算法的字符串查找与替换.doc

数据结构实验报告评分满分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中的字符替换程序测试简要报告：(1) 无a测试程序输入输出结论程序输出结果与期望输出结果相符。(2) a、b等长度测试程序输入输出 结论程序输出结果与期望输出结果相符。(3) a、b不等长度测试程序输入输出 结论程序输出结果与期望输出结果相符。源程序代码：#include #include using namespace std;void get_nextval(char *t, int nextval) /get_nextval函数int j = 1, k = -1;nextval0 = -1;while (tj) if (k = -1 | tj - 1 = tk)if (t+k = tj) nextvalj+ = nextvalk;else nextvalj+ = k;else k = nextvalk;int index_kmp(char *s, char *t, int next) /KMP查找函数int i = 0, j = 0;while (si & tj) if (j = -1 | si = tj) i+; j+;else j = nextj;if (!tj) return i - j;return -1;void replace(char *s, char *b, int position, int lena) int i, j, lens = strlen(s), lenb = strlen(b);if (lenb lena) /将a以后的字符串向后挪lenb-lena个位置for (i = lens + lenb - lena, j =lens; j = position+lena; i-, j-) si = sj;else if (lenb lena) /将a以后的字符向前挪lenb-lana个位置for (i = position + lenb, j = position+lena; j = lens; i+, j+)si = sj;i = 0;while (bi) sposition+ = bi+;int main() char s40, a40, b40, *p;int next40, count = 0;while (1) cout s; p = s;cout a;get_next(a, next);while (strlen(p)=strlen(a) /剩余字符串长度小于p时停止查找int position = index_kmp(p, a, next);if (position = -1) break;count+;/count计找到a的次数if (count = 1) /找到第一个a时输入bcout find the first Position: position b; replace(p, b, position, strlen(a);cout endl s endl;p += position + strlen(b);/将p定位到position加上a的长度之后，从那之后继续寻找