实验04：串应用KMP算法.ppt

实验五 串应用--KMP算法实验 实验串应用--KMP算法实验 数据结构实验与课程设计 2012年xx月xx日 深圳大学计算机系朱安民 一、实验目的 * 一、实验目的 掌握串结构的基本概念 掌握串结构的存储结构 掌握顺序串类的定义 掌握串的KMP模式匹配算法及其C++语言的实现 实验五 串应用--KMP算法实验 二、实验要求 * 二、实验要求 熟悉C++语言编程 熟练使用C++语言实现顺序串类的定义 完成KMP的模式匹配算法 实验五 串应用--KMP算法实验 1、问题描述 * 三、实验内容 在主串S中，从位置pos开始查找是否存在模式子串T，如果存在，则返回主串中的位置，如果不存在，则返回0。 实验五 串应用--KMP算法实验 2、算法 * 三、实验内容 KMP算法思想： 将主串和模式子串从第一位进行一一比较，当一趟匹配过程中出现字符比较不等(失配)时，不需回溯主串指针i，而是利用已经得到的“部分匹配”的结果，将模式子串向右“滑动”尽可能远的一段距离(next[j])后，继续进行比较。 实验五 串应用--KMP算法实验 具体方法--求next[j] * 按照下列公式求出模式子串t的next[j]函数 -1 当j=0时 next[j]= max{k|0kj且t0t1…tk-1=tj-ktj-k+1…tj-1}当此集合非空 　 0 其它情况 设i为主串当前比较字符的下标，j为模式子串当前比较字符的下标，令i的初始值为start，j的初始值为0。 实验五 串应用--KMP算法实验 具体方法—KMP算法： * (1) 当si=tj时，i和j分别增1再继续比较； 否则，i不变，j改变为next[j]值再继续比较； (2) 这样的循环过程直到变量i大于等于主串的长度或j大于等于子串的长度时终止。若变量i大于等于主串的长度，则返回0，匹配不成功；若变量j大于等于子串的长度，则返回匹配时主串位置，匹配成功。 实验五 串应用--KMP算法实验 3、输入 * 三、实验内容 第一个输入t，表示有t个实例 第二行输入第1个实例的主串，第三行输入第1个实例的模式串 以此类推 实验五 串应用--KMP算法实验 4、输出 * 三、实验内容 第一行输出第1个实例的模式串的next值 第二行输出第1个实例的匹配位置，位置从1开始计算，如果匹配成功输出位置，匹配失败输出0 以此类推 实验五 串应用--KMP算法实验 5、输入样本 * 三、实验内容 3 qwertyuiop tyu aabbccdd ccc aaaabababac abac 实验五 串应用--KMP算法实验 6、输出样本 * 三、实验内容 -1 0 0 5 -1 0 1 0 -1 0 0 1 8 实验五 串应用--KMP算法实验 * 四、实验步骤 1、顺序串类的定义，包括构造函数、析构函数 2、模式子串的next[j]函数 3、KMP匹配算法函数 4、主程序 实验五 串应用--KMP算法实验 * 1 串类定义 实验五 串应用--KMP算法实验 * 2 赋值与next函数 实验五 串应用--KMP算法实验 * 3 KMP内部函数 实验五 串应用--KMP算法实验 * 4 KMP外部函数 实验五 串应用--KMP算法实验 * 5 主函数 实验五 串应用--KMP算法实验 实验五 串应用--KMP算法实验