主要是针对字符串的匹配算法进行解说
有关字符串的基本知识
串（string或字符串）是由零个或多个字符组成的有限序列，一般记为
当中s是串的名，用单引號括起来的字符序列是串的值；ai（1&=i&=n）能够是字母、数值或其它字符。串中字符的数组 n称为串的长度。零个字符的串称为空串，它的长度为0
串中随意个连续的字符组成的子序列称为该串的子串。包括子串的串相应的称为主串。通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。
以下主要说一下串的模式匹配算法
传统的串匹配法
算法的基本思想是：从主串S的第pos个字符起和模式的第一个字符比較，若相等，则继续逐个比較兴许字符；否则从主串的下一个字符起再又一次和模式的字符比較。依次类推，直至模式T中的每一个字符依次和主串S中的一个连续的字符序列相等，则匹配成功，函数值为和模式T中第一个字符相等的字符在主串S中的序号，否则称匹配不成功。函数值为零。
此算法在最坏情况下的时间复杂度为O(m*n)
模式匹配的一种改进算法（KMP算法）
网上一比較易懂的解说
字符串匹配是计算机的基本任务之中的一个。
举例来说，有一个字符串”BBC ABCDAB ABCDABCDABDE”，我想知道，里面是否包括还有一个字符串”ABCDABD”？
很多算法能够完毕这个任务，Knuth-Morris-Pratt算法（简称KMP）是最经常使用的之中的一个。它以三个发明者命名，起头的那个K就是著名科学家Donald Knuth。
以下，我用自己的语言，试图写一篇比較好懂的KMP算法解释。
首先，字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符，进行比較。由于B与A不匹配。所以搜索词后移一位。
由于B与A不匹配。搜索词再往后移。
就这样，直到字符串有一个字符，与搜索词的第一个字符同样为止。
接着比較字符串和搜索词的下一个字符，还是同样。
直到字符串有一个字符，与搜索词相应的字符不同样为止。
这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比較。这样做尽管可行，可是效率非常差，由于你要把”搜索位置”移到已经比較过的位置，重比一遍。
一个基本事实是，当空格与D不匹配时，你事实上知道前面六个字符是”ABCDAB”。KMP算法的想法是，设法利用这个已知信息。不要把”搜索位置”移回已经比較过的位置，继续把它向后移，这样就提高了效率。
怎么做到这一点呢？能够针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是怎样产生的，后面再介绍，这里仅仅要会用就能够了。
已知空格与D不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知。最后一个匹配字符B相应的”部分匹配值”为2，因此依照以下的公式算出向后移动的位数：
　　移动位数 = 已匹配的字符数 - 相应的部分匹配值
由于 6 - 2 等于4。所以将搜索词向后移动4位。
由于空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（”AB”），相应的”部分匹配值”为0。所以。移动位数 = 2 - 0，结果为 2。于是将搜索词向后移2位。
由于空格与A不匹配，继续后移一位。
逐位比較，直到发现C与D不匹配。于是。移动位数 = 6 - 2，继续将搜索词向后移动4位。
逐位比較。直到搜索词的最后一位，发现全然匹配。于是搜索完毕。假设还要继续搜索（即找出所有匹配）。移动位数 = 7 - 0。再将搜索词向后移动7位。这里就不再反复了。
以下介绍《部分匹配表》是怎样产生的。
首先，要了解两个概念：”前缀”和”后缀”。 “前缀”指除了最后一个字符以外。一个字符串的所有头部组合；”后缀”指除了第一个字符以外。一个字符串的所有尾部组合。
“部分匹配值”就是”前缀”和”后缀”的最长的共同拥有元素的长度。以”ABCDABD”为例。
　　－　“A”的前缀和后缀都为空集。共同拥有元素的长度为0；
　　－　“AB”的前缀为[A]。后缀为[B]。共同拥有元素的长度为0；
　　－　“ABC”的前缀为[A, AB]，后缀为[BC, C]，共同拥有元素的长度0；
　　－　“ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共同拥有元素的长度为0；
　　－　“ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共同拥有元素为”A”，长度为1；
　　－　“ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]。后缀为[BCDAB, CDAB, DAB, AB, B]。共同拥有元素为”AB”，长度为2；
　　－　“ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共同拥有元素的长度为0。
“部分匹配”的实质是，有时候。字符串头部和尾部会有反复。比方，”ABCDAB”之中有两个”AB”，那么它的”部分匹配值”就是2（”AB”的长度）。搜索词移动的时候，第一个”AB”向后移动4位（字符串长度-部分匹配值），就能够来到第二个”AB”的位置。
求字符串 ‘ababaabab’的next和nextval，结果例如以下
（1）计算next
计算next的时候须要遵循的规则例如以下
next[j] = 0
B、假设存在
Max{ k | k 属于 （1，j-1） 且‘P1…Pk-1’= ‘Pj-k+1…Pj-1’ }
（next[j] = k）
C、其它情况
next[j] = 1
( 1, k-1 )
str(1,k-1)
( j-k+1 , j-1 )
str( j-k+1, j-1)
（2）计算nextval
nextval[i]的求解须要比較s中next[i]所在位置的字符是否与s[i]的字符一致。假设一致则用s[next[i]]的nextval的值作为nextval[i]。假设不一致，则用next[i]做为nextval[i]。
s[ next[i] ]
nextval[i]
next[i] = 0
next[i] = 1
s[ next[i] ]的nextval = 0
s[2]nextval = 1
s[2]nextval = 0
next[6] = 4
s[2] nextval = 1
s[3] nextval = 0
s[4]nextval = 1
该代码參考 数据结构（C语言版） 严蔚敏 吴伟民 编著。。。
KMP algorithm
#include&iostream&
#include&string.h&
the next index data of the model string s_mode
s_mode: the string
: the next array
: the length of the string
void get_next( string s_mode, int *next, int len )
int i = 1;
int j = 0;
next[1] = 0;
while( i&len )
if( j==0 || s_mode[i] == s_mode[j] )
if( i&len ) break;
if( j&len ) break;
j = next[j];
for( int i=1; i& i++ )
cout && next[i] && " ";
利用模式串s_mode中的next函数求s_model在主串 s_primary中第pos个字符之后的位置
int Index_KMP( string s_primary, string s_mode, int pos, int *next )
int j = 1;
int len_p = s_primary.size();
int len_m = s_mode.size();
while( i & len_p && j & len_m )
if( j == 0 || s_primary[i] == s_mode[j] )
j = next[j];
if( j &= len_m )
return i - len_m;
output function to check the result
void output( string s_primary, string s_mode, int len, int *next, int index )
cout && "s_primary = " && s_primary &&
cout && "s_mode = " && s_mode &&
for( int i=1; i& i++ )
cout && next[i] && " ";
cout && "index = " && index &&
int main()
string s_primary = " acabaabaabcacaabc";
string s_mode
= " abaabcac";
int len = s_mode.size() ;
int *next = new int[len];
get_next( s_mode, next, len );
int tmp = Index_KMP( s_primary, s_mode, 1, next );
output( s_primary, s_mode, len, next, tmp );
【1】字符串匹配的KMP算法 - 阮一峰的网络日志
【2】KMP算法具体解释 - joylnwang的专栏 - 博客频道 - CSDN.NET
【3】经典算法研究系列：六、教你初步了解KMP算法、updated - 结构之法 算法之道 - 博客频道 - CSDN.NET
阅读(...) 评论()高校数据结构考研试题_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
高校数据结构考研试题
上传于|0|0|文档简介
&&名牌大学计算机专业数据结构考研试题
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩25页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢君，已阅读到文档的结尾了呢~~
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
数据结构习题
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口第二次作业一、选择题；1、栈和队列的相同之处是；A.元素的进出满足先进后出C.只允许在端点进行插；B.元素的进出满足后进先出；D.无共同点；2、设栈S和队列Q的初始状态为空,元素e1，e2；A.6；B.4；C.3；D.2；3、队列通常采用的两种存储结构是(A)；A.顺序存储结构和链式存储结构B.散列方式和索引；C.链表存储结构和线性存储结构D.线性存储结构和
第二次作业 一、选择题
1、栈和队列的相同之处是。
A.元素的进出满足先进后出
C.只允许在端点进行插入和删除操作
B.元素的进出满足后进先出
D.无共同点
2、设栈S 和队列Q 的初始状态为空,元素e1，e2，e3，e4，e5 和e6 依次通过栈，一个元素出栈后即进入队列Q,若6 个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S 的容量至少应该是
3、队列通常采用的两种存储结构是( A)。
A. 顺序存储结构和链式存储结构
B.散列方式和索引方式
C. 链表存储结构和线性存储结构
D.线性存储结构和非线性存储结构 4、循环队列SQ队满的条件是
A. SQ-&rear==SQ-&front
B. SQ-&rear==0
B. (SQ-&rear+1)%MAXLEN==SQ-&front
D. SQ-&front==0
5、若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为
6、链栈与顺序栈相比，有一个较为明显的优点是
A. 通常不会出现满栈的情况 C. 插入操作更加方便
B. 通常不会出现栈空的情况
D. 删除操作更加方便
7、设用一个大小为M=60的顺序表A[M]表示一个循环队列，如果当前的尾指针rear=32，头指针front=15，则当前循环队列的元素的个数为
8、串是一种特殊的线性表，其特殊性体现在
A. 可以顺序存储 C. 可以链式存储 A. O(m)
B. 数据元素是一个字符 D. 数据元素可以是多个字符
D. O(m×n)
9、设主串的长度为n，模式串的长度为m，则串匹配的KMP算法的时间复杂度为
C. O(m+n) C. 0112
10、已知串S=“abab”，其Next数组值为
11、若字符串“ABCDEFG”采用不带表头的链式存储，每个结点保存一个字符。假设每个字符占用1个字节，每个指针占用两个字节，则该字符串的存储密度为
12、在双向链表中，在指针p所指的结点前插入一个指针q所指向的结点，操作是。
A. p-&Prior=q; q-&Next=p; p-&Prior-&next=q; q-&Prior=q; B. p-&Prior=q; p-&Prior-&next=q; q-&next=p; q-&Prior=p-&P C. q-&Next=p; q-&Prior=p-&P p-&Prior-&Next=q; p-&Prior=q;
D. q-&Prior=p-&P q-&Next=q; p-&Prior=q; p-&Next=q;
13、已知循环队列存储在一维数组A[0…n-1]中，且队列非空时front和rear分别指向对头元素和队尾元素，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是
D. n-1, n-1
14、某队列允许在两端进行入队操作，但仅允许在一端进行出队操作（称为输出受限的双端队列），若a, b, c, d, e元素依次进队，则不可能得到的顺序是
二、填空题
1、对于循环向量的循环队列，求队列长度的公式为。 2、栈的逻辑特点是 后进先出
。队列的逻辑特点是许在它们的
出插入和删除数据元素，区别是
出栈在顶端，出队列在头部
A. bacde A. 1
C. dbcae D. 4
15、在双向链表中间插入一个结点时，需要修改修改 16、在按行优先顺序存储的三元组表中，下述陈述错误的是
A. 同一行的非零元素，是按列号递增次序存储的 B. 同一列的非零元素，是按行号递增次序存储的 C. 三元组表中三元组行号是非递减的 D. 三元组表中三元组列号是非递减的 A. 矩阵中非零元素的值 B. 矩阵中数据元素的行号和列号 C. 矩阵中数据元素的行号、列号和值 D. 矩阵中非零数据元素的行号、列号和值 A. 表达变得简单
B. 对矩阵元素的存取变得简单 D. 减少不必要的存储空间 B. 能否使用原子项 D. 是否能为空
D. (b, c, d)
17、在稀疏矩阵的三元组表示法中，每个三元组表示。
18、对特殊矩阵采用压缩存储的目的主要是为了
C. 去掉矩阵中的多余元素 A. 能否使用子表 C. 表的长度 A. a
19、广义表是线性表的推广，它们之间的区别在于
20、已知广义表(a, b, c, d)的表头是，表尾是
C. (a, b, c, d)
21、下面说法不正确的是
A. 广义表的表头总是一个广义表 C. 广义表难以用顺序存储结构表示 A. (
B. 广义表的表尾总是一个广义表 D. 广义表可以是一个多层次的结构
D. (( ), ( ), ( ))
22、若广义表A满足Head(A)=Tail(A)，则A为。
C. (( ),( ))
3、链队列LQ为空时，4、在一个链队列中，若队首指针为front，队尾指针为rear，则判断该队列只有一个结点的条件为
front-&next
5、设串S=“Ilikecomputer”，T=“com”，则 6、在KMP算法中，next[j]只与 7、字符串“ababaab“的Next数组值是
8、稀疏矩阵一般压缩存储的方式有三种，分别是、
稀疏矩阵的链式结构
9、二维数组M中每个元素的长度是3字节，行下标i从0~7，列下标j从0～9，从首地址&M[0][0]开始连续存放在存储器中。若按行优先的方式存放，元素M[7][5]的起始地址为 ；若按列优先方式存放，元素M[7][5]的起始地址为
10、广义表(a, (a, b), d, e, ((i, j), k))的长度是。
11、设广义表A(
( ), (a, (b), c)
)1，则Cal(Cdr(Cal(Cdr(Cal(A))))=
三、设有一个循环队列Queue，只有头指针front，不设尾指针，另设一个含有元素个数的计数器count，试写出相应的判断队列空、判断队列满、出队算法和入队算法。 要求：
1、定义相应的循环队列的型（只有头指针，没有尾指针，但有一个元素个数的计数器）；
2、定义该队列的四个算法：判断队列空、判断队列满、出队算法和入队算法； 3、在main函数验证算法的正确性。 ////
#include &iostream&
class Queue{
_font = len = 0;
ele data[10]; ele* _
bool full(){
bool empty(){
void pop_font(){
} int font(){
_font = data + (_font - data + 1)%10; len--;
return (len == 0); return (len &= 10);
data[(_font-data+len)%10] = len++;
int main(int argc, char *argv[]) {
for ( i = 0; i & 10; i++) {
for ( i = 0; i & 10; i++) {
cout&&&=====欢乐的分割线=====&&& for ( i = 0; i & 10; i++) {
for ( i = 0; i & 10; i++) {
cout&&q.font()&& q.pop_font(); q.push_back(i); cout&&q.font()&& q.pop_font(); q.push_back(i);
四、设主串T=“abcaabbabcabaacbacba“，模式为p=“abcabaa”。
1、计算模式p的nextval函数值
2、不写算法，只画出利用KMP算法进行模式匹配时，每一趟的匹配过程。 要求：
1、写出模式p的nextval值；
2、画出KMP算法的每一趟匹配过程（可参照教材P61从第8行开始的内容）； 3、不需要编写程序。 0001211
三亿文库包含各类专业文献、外语学习资料、生活休闲娱乐、幼儿教育、小学教育、高等教育、专业论文、行业资料、39计130121第二次作业等内容。　 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
【精品】数据结构1800例题与答案之串
下载积分：820
内容提示：【精品】数据结构1800例题与答案之串
文档格式：DOC|
浏览次数：36|
上传日期： 06:15:17|
文档星级：
全文阅读已结束，如果下载本文需要使用
 820 积分
下载此文档
该用户还上传了这些文档
【精品】数据结构1800例题与答案之串
官方公共微信