数据结构实验报告
进队
deQueue（）
出队
3、实验数据与结果
2.3实验3(exp4-3)
1、题目
编写一个程序exp4-3.cpp，实现顺序串的各种匹配模式运算，并在此基础上完成如下功
能：
(1) 建立“abcabcdabcdeabcdefabcdefg”目标串和“abcdeabcdefab”模式串t；
13
数据结构实验报告
(2) (3) (4) (5) 简单匹配算法求t在s中过的位置； 由模式串t求出next的值和nextval的值 采用KMP算法求t在s中的位置
采用改进的KMP算法求t在s中的位置
2、算法设计
(1) 设计思路
本题的关键是KMP算法的思路以及改进后的KMP算法思路，一般的模式串匹配算法
是按个扫描目标串和模式串，如果不匹配，则目标串跳转到下一个字母重新匹配，这在很大程度上做了很多重复匹配的工作，所以KMP算法就是在此基础上的改进
(2) 程序关系图
StrAssignDispStrIndexmainGetNextKMPIndexGetNextvalKMPIndexpro
(3) 函数功能描述 StrAssign（）
14
数据结构实验报告
将str[]中的字符串复制到s中 DispStr（）
输出字符串 Index（）
15
数据结构实验报告
简单的匹配算法
GetNext（）
根据模式串求出下一个字符的下标
KMPIndex（）
16