下载文档原格式
2 KMP算法：KMP算法是由D.E.Knuth（克努特），J.H.Morris（莫里斯），V.R.Pratt（普拉特）等人共同提出的，该算法主要消除了主串指针(i指针)的回溯，利用已经得到的部分匹配结果将模式串右滑尽可能远的一段距离再继续比较，从而使算法效率有某种程度的提高，O(n+m)。
先从例子入手（p82）：按Brute-Force算法i=i-j+2=2-2+2=2,j=1按Brute-Force算法i=i-j+2=2-1+2=3,j=1按Brute-Force算法i=i-j+2=8-6+2=4,j=1,但从已匹配的情况看，模式串在t[6]即“c”前的字符都是匹配的，再看已匹配的串“abaab”,t[1]t[2]与t[4]t[5]相同，那么，因为t[4]t[5]与原串s[6]s[7]匹配，所以t[1]t[2]必然与原串s[6]s[7]匹配，因此说t[3]可以直接与s[8]匹配，按KMP 算法i=8,j=3匹配成功。
从上例看出在匹配不成功时，主串指针i不动，j指针也不回到第一个位置，而是回到一个恰当的位置，如果这时让j指针回到第一个位置，就可能错过有效的匹配，所以在主串指针i不动的前提下，j指针回到哪个位置是问题的关键，既不能将j右移太大，而错过有效的匹配，另一方面，又要利用成功的匹配，将j右移尽可能地大，而提高匹配的效率，因此问题的关键是寻找模式串自身的规律。
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////。
和直接比较若不满足和直接比较所以：满足：，设1i i 12112111112121s ),2(;s )1(""")"2(""")"1(""""t t j k t t t t t t t t s s t t t t s s s s k j k j k j k j i j i m n <<====-+-+----+-////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////设s=” s 1 s 2 ... s n ”， t=” t 1 t 2 ... t m ”，在匹配过程中，当s i ≠ t j (1≤i ≤n-m+1,1≤j ≤m)时，存在（前面的j-1个字符已匹配）：” s i-j+1 ... s i-1 ” =” t 1 t 2 ... t j-1 ” (1) 若模式中存在可互相重叠的最长的真子串，满足： ” t 1 t 2 ... t k-1 ”=”t j-k+1 t j-k+2 ... t j-1 ” (2) 其中真子串最短可以是t 1 ，即 t 1。
第4章串1．采用顺序结构存储串，编写一个实现串通配符匹配的算法pattern______index（），其中的通配符只有“？”，它可以和任一字符匹配成功，例如，pattern______index（″? re″，″there are″）返回的结果是2。
答：本题的基础是Brute—Force模式匹配算法，只是增加了“？”的处理功能。
对应的算法如下：2．有两个串s1和s2，设计一个算法求这样一个串，该串中的字符是s1和s2中的公共字符。
答：扫描s1，对于当前字符s1.data[i]，若在s2中，则将其加入到串s3中。
最后返回s3串。
对应的算法如下：3．设目标为t=’abcaabbabcabaacbacba’，模式p=’abcabaa’。
（1）计算模式P的nextval函数值。
（2）不写算法，只画出利用KMP算法进行模式匹配时的每一趟匹配过程。
答：（1）先计算next数组，在此基础上求nextval数组，如表4-1所示。
表4-1 计算next数组和nextval数组（2）采用KMP算法求子串位置的过程如下（开始时i=0，j=0）：第1趟匹配：此时i=4，j=4，匹配失败，而nextval[4]=0，则i=4，j=nextval[4]=0，即：第2趟匹配：此时i=6，j=2，匹配失败，而nextval[2]=0，则i=6，j=nextval[2]=0，即：第3趟匹配：此时i=6，j=0，匹配失败，而nextval[0]=-1，则i=6，j=nextval[0]=-1。
因j=-1，执行i=i+1=7，j=j+1=0，即：第4趟匹配：此时i=14，j=7，匹配成功，返回v=i-t．1ength=14-7=7。
上机实验题4实验题1编写一个程序algo4-1.cpp，实现顺序串的各种基本运算，并在此基础上设计一个程序exp4-1.cpp完成如下功能：（1）建立串s=″abcdefghefghijklmn″和串sl=″xyz″；（2）输出串s；（3）输出串s的长度；（4）在串s的第9个字符位置插入串s1而产生串s2；（5）输出串s2；（6）删除串s第2个字符开始的5个字符而产生串s2；（7）输出串s2；（8）将串s第2个字符开始的5个字符替换成串s1而产生串s2；（9）输出串s2；（10）提取串s的第2个字符开始的10个字符而产生串s3；（11）输出串s3；（12）将串s1和串s2连接起来而产生串s4；（13）输出串s4。
第四章串一、选择题1．下面关于串的的叙述中，哪一个是不正确的（）（2 分）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2 若串S=‘ABCDEFG’, S2=‘9898’,S3=‘###’,S4=‘012345’,执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2))) 其结果为（）（7 分）A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345E．ABC###G1234 F．ABCD###1234 G．ABC###012343．设有两个串p 和q，其中q 是p 的子串，求q 在p 中首次出现的位置的算法称为（）A．求子串B．联接C．匹配D．求串长（2 分）4．已知串S=‘aaab’,其Next 数组值为（）。
（2 分）A．0123 B．1123 C．1231 D．12115．串‘ababaaababaa’的next 数组为（）。
A．0 B．012121111212 C．0 D．06．字符串‘ababaabab’的nextval 为（）A．(0,1,0,1,04,1,0,1) B．(0,1,0,1,0,2,1,0,1)C．(0,1,0,1,0,0,0,1,1) D．(0,1,0,1,0,1,0,1,1 )（2 分）7．模式串t=‘abcaabbcabcaabdab’，该模式串的next 数组的值为（），nextval 数组的值为（）。
A．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B．0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2C．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2E．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F．0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1（2 分）8．若串S=’software’,其子串的数目是（）。
2022年东北电力大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、n个结点的完全有向图含有边的数目（）。
A.n*nB.n(n+1)C.n/2D.n*(n-1)2、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。
A.插入B.选择C.希尔D.二路归并3、以下数据结构中，（）是非线性数据结构。
A.树B.字符串C.队D.栈4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。
A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改5、已知串S='aaab'，其next数组值为（）。
A.0123B.1123C.1231D.12116、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。
假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。
初始时为空，下列判断队空和队满的条件中，正确的是（）。
A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod MB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod MD．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）7、下列关于无向连通图特性的叙述中，正确的是（）。
Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ8、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。
A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个9、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。
![[计算机软件及应用]栈的应用和串图](https://img.taocdn.com/s1/m/62d61f359ec3d5bbfc0a74c2.png)
2022年安徽师范大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、已知广义表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e的运算是（）。
A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。
A.13B.33C.18D.403、静态链表中指针表示的是（）。
A.下一元素的地址B.内存储器的地址C.下一元素在数组中的位置D.左链或右链指向的元素的地址4、动态存储管理系统中，通常可有（）种不同的分配策略。
A.1B.2C.3D.45、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。
A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)6、下列关于无向连通图特性的叙述中，正确的是（）。
Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ7、下列选项中，不能构成折半查找中关键字比较序列的是（）。
A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4508、设X是树T中的一个非根结点，B是T所对应的二叉树。
在B中，X是其双亲的右孩子，下列结论正确的是（）。
A.在树T中，X是其双亲的第一个孩子B.在树T中，X一定无右兄弟C.在树T中，X一定是叶结点D.在树T中，X一定有左兄弟9、每个结点的度或者为0或者为2的二叉树称为正则二叉树。
n个结点的正则二叉树中有（）个叶子。
A.log2nB.（n－1）/2C.log2n+1D.（n＋1）/210、就平均性能而言，目前最好的内排序方法是（）排序法。
计算机专业基础综合数据结构（串）历年真题试卷汇编1(总分：58.00，做题时间：90分钟)一、填空题(总题数：12，分数：24.00)1.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为(1)，又称P为(2)。
【西安电子科技大学1998二、5(16／6分)】__________________________________________________________________________________________ 正确答案：(正确答案：(1)模式匹配 (2)模式串)2.串是一种特殊的线性表，其特殊性表现在(1) ；串的两种最基本的存储方式是(2)、(3)；两个串相等的充分必要条件是(4)。
【中国矿业大学2000一、3(4分)】__________________________________________________________________________________________ 正确答案：(正确答案：(1)其数据元素都是字符(2)顺序存储(3)链式存储(4)串的长度相等且两串中对应位置的字符也相等)3.使用“求子串”subString(S，pos，len)和“联结”concat(S1，s2)的串操作，可从串s=‘conduction’中的字符得到串t=”cont”，则求t的串表达式为__________。
【北京工业大学2005二、4(3分)】__________________________________________________________________________________________ 正确答案：(正确答案：t=concat(subStIling(s，1，3)，subString(s，7，1)))4.下列程序读入无符号十六进制数(出现的字母为小写)，将其转换为十进制数输出。
请将程序空缺部分补全。
int f(char *s) {int n=0，i；for(i=0；s[i]!="＼0"; i++)n=n*16+(1)；return n；} main() {char s[10]； scanf(“％s”，s)；printf(“％d＼n”(2) )； }【浙江大学2002二(6分)】__________________________________________________________________________________________ 正确答案：(正确答案：(1)(s[i]>=977 s[i]一87：s[i]-48) ／／"a"到"f"的ASCII码是97到102 (2)f(s)) 5.已知U=‘xyxyxyxxyxy’；t=‘xxy’；ASSIGN(S，U)；ASSIGN(V，SUBSTR(S，INDEX(s，t)，LENCt)+1)),ASSIGN(m，‘ww’)求REPLACE(S，y，m)=__________。
第四章串一、选择题1．函数substr(“DATASTRUCTURE”，5，9)的返回值为（）。
A. “STRUCTURE”B.“DATA”C. “ASTRUCTUR”D. “DATASTRUCTURE”2．字符串的长度是指（）。
A. 串中不同字符的个数B. 串中不同字母的个数C. 串中所含字符的个数D. 串中不同数字的个数3．两个字符串相等的充要条件是（）。
A. 两个字符串的长度相等B. 两个字符串中对应位置上的字符相等C. 同时具备(A)和(B)两个条件D. 以上答案都不对4．关于串的叙述中，正确的是（）A．空串是只含有零个字符的串B.空串是只含有空格字符的串C.空串是含有零个字符或含有空格字符的串D.串是含有一个或多个字符的有穷序列5．下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列 B．空串是由空格构成的串C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储6．设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作( ) A．求子串 B.判断是否相等 C．模型匹配 D.连接7．若串S=’software’,其子串的数目是( )。
A．8 B．37 C．36 D．98．串的长度是指（）A．串中所含不同字母的个数 B．串中所含字符的个数C．串中所含不同字符的个数 D．串中所含非空格字符的个数9．串是一种特殊的线性表，其特殊性体现在( )。
A．数据元素是一个字符 B. 可以顺序存储C. 数据元素可以是多个字符D. 可以链接存储10．下面关于串的的叙述中，哪一个是不正确的（B）A. 串是字符的有限序列B. 空串是由空格构成的串C. 模式匹配是串的一种重要运算D. 串既可以采用顺序存储，也可以采用链式存储11．若串＝‘software’，其非平凡子串（非空且不同于串本身）的数目是（C）A. 8 B. 37 C. 35 D. 912．串是一种特殊的线性表，其特殊性体现在（B）A. 可以顺序存储B. 数组元素是一个字符C. 可以连续存储D. 数据元素可以是多个字符13. 下面关于串的的叙述中，哪一个是不正确的？（B）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储二、填空题1．两个串是相等的，当且仅当两个串的长度相等且___对应位置_____的字符都相同。
2022年江苏理工学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。
A.60B.66C.18000D.332、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
A.快速排序B.堆排序C.归并排序D.直接插入排序3、链表不具有的特点是（）。
A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比4、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。
A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)5、动态存储管理系统中，通常可有（）种不同的分配策略。
A.1B.2C.3D.46、下列选项中，不能构成折半查找中关键字比较序列的是（）。
A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4507、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。
A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝28、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。
A.107B.108C.214D.2159、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。
A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个10、分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（）。
A.（100，80，90，60，120，110，130）B.（100，120，110，130，80，60，90）C.（100，60，80，90，20，110，130）D.（100，80，60，90，120，130，110）二、填空题11、在有n个顶点的有向图中，每个顶点的度最大可达______。
第1章绪论5．选择题：CCBDCA6．试分析下面各程序段的时间复杂度。
（1)O（1）（2）O(m＊n）（3）O（n2）（4)O（log3n）（5)因为x++共执行了n—1+n—2+……＋1= n(n—1)/2，所以执行时间为O(n2)（6）O(n）第2章线性表1．选择题babadbcabdcddac2．算法设计题(6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。
ElemType Max （LinkList L ）｛if(L—〉next==NULL) return NULL；pmax=L-〉next；//假定第一个结点中数据具有最大值p=L-〉next—>next；while(p ！= NULL ){//如果下一个结点存在if（p->data > pmax—>data) pmax=p；p=p->next；｝return pmax-〉data;（7)设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间.void inverse(LinkList ＆L) ｛// 逆置带头结点的单链表Lp=L-〉next；L->next=NULL；while （p）｛q=p—>next；// q指向＊p的后继p->next=L—>next;L—>next=p; // *p插入在头结点之后p = q;｝}（10)已知长度为n的线性表A采用顺序存储结构,请写一时间复杂度为O(n)、空间复杂度为O（1）的算法，该算法删除线性表中所有值为item的数据元素.［题目分析］在顺序存储的线性表上删除元素,通常要涉及到一系列元素的移动（删第i个元素，第i+1至第n个元素要依次前移)。
本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。
因此可以考虑设头尾两个指针（i=1，j=n）,从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。
记得大学时自己也总结出了这种算法的，手动计算，数据结构的书都丢了，还好在网上找会
了同样的算法
特记下：
int get_nextval(SString T,int &nextval[ ]){
//求模式串T的next函数修正值并存入数组nextval。
i=1; nextval[1]=0; j=0;
while(i
++i;++j;
if (T[i]!=T[j]) nextval[i]=j;
else nextval[i]=nextval[j];
}
else j=nextval[j];
}
}//get_nextval
根据这段程序来求nextval的值是可以方便计算出来，但如果是应付考研试题或者期
末考试就有点麻烦了。而如果记住我推荐的方法，那么任何时候都可以很方便地求解nextval
了。
首先看看next数组值的求解方法。
例如： 模式串 a b a a b c a c
next值 0 1 1 2 2 3 1 2
nextval值
next数组的求解方法是：第一位的next值为0，第二位的next值为1，后面求解每
一位的next值时，根据前一位进行比较。首先将前一位与其next值对应的内容进行比较，
如果相等，则该位的next值就是前一位的next值加上1；如果不等，向前继续寻找next值
对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相
等为止，则这个位对应的值加上1即为需求的next值；如果找到第一位都没有找到与前一
位相等的内容，那么需求的位上的next值即为1。
看起来很令人费解，利用上面的例子具体运算一遍。
1.前两位必定为0和1。
2.计算第三位的时候，看第二位b的next值，为1，则把b和1对应的a进行比较，
不同，则第三位a的next的值为1，因为一直比到最前一位，都没有发生比较相同的现象。
3.计算第四位的时候，看第三位a的next值，为1，则把a和1对应的a进行比较，
相同，则第四位a的next的值为第三位a的next值加上1。为2。因为是在第三位实现了其
next值对应的值与第三位的值相同。
4.计算第五位的时候，看第四位a的next值，为2，则把a和2对应的b进行比较，
不同，则再将b对应的next值1对应的a与第四位的a进行比较，相同，则第五位的next
值为第二位b的next值加上1，为2。因为是在第二位实现了其next值对应的值与第四位的
值相同。
5.计算第六位的时候，看第五位b的next值，为2，则把b和2对应的b进行比较，
相同，则第六位c的next值为第五位b的next值加上1，为3，因为是在第五位实现了其
next值对应的值与第五位相同。
6.计算第七位的时候，看第六位c的next值，为3，则把c和3对应的a进行比较，
不同，则再把第3位a的next值1对应的a与第六位c比较，仍然不同，则第七位的next
值为1。
7.计算第八位的时候，看第七位a的next值，为1，则把a和1对应的a进行比较，
相同，则第八位c的next值为第七位a的next值加上1，为2，因为是在第七位和实现了其
next值对应的值与第七位相同。
在计算nextval之前要先弄明白，nextval是为了弥补next函数在某些情况下的缺陷
而产生的，例如主串为“aaabaaaab”、模式串为“aaaab”那么，比较的时候就会发生一些浪
费的情况：比较到主串以及模式串的第四位时，发现其值并不相等，据我们观察，我们可以
直接从主串的第五位开始与模式串进行比较，而事实上，却进行了几次多余的比较。使用
nextval可以去除那些不必要的比较次数。
求nextval数组值有两种方法，一种是不依赖next数组值直接用观察法求得，一种
方法是根据next数组值进行推理，两种方法均可使用，视更喜欢哪种方法而定。
我们使用例子“aaaab”来考查第一种方法。
1.试想，在进行模式匹配的过程中，将模式串“aaaab”与主串进行匹配的时候，如
果第一位就没有吻合，即第一位就不是a，那么不用比较了，赶快挪到主串的下一位继续与
模式串的第一位进行比较吧，这时，模式串并没有发生偏移，那么，模式串第一位a的nextval
值为0。
2.如果在匹配过程中，到第二位才发生不匹配现象，那么主串的第一位必定是a，而
第二位必定不为a，既然知道第二位一定不为a，那么主串的第一、二两位就没有再进行比
较的必要，直接跳到第三位来与模式串的第一位进行比较吧，同样，模式串也没有发生偏移，
第二位的nextval值仍然为0。
3.第三位、第四位类似2的过程，均为0。
4.如果在匹配过程中，直到第五位才发生不匹配现象，那么主串的第一位到第四位
必定为a，并且第五位必定不为b，可是第五位仍然有可能等于a。如果万一第五位为a，那
么既然前面四位均为a，所以，只要第六位为b，第一个字符串就匹配成功了。所以，现在
的情况下，就是看第五位究竟是不是a了。所以发生了下面的比较：
1 2 3 4 5 6
a a a a * *
a a a a b
a a a a b
前面的三个a都不需要进行比较，只要确定主串中不等于b的那个位是否为a，即
可以进行如下的比较：如果为a，则继续比较主串后面一位是否为b；如果不为a，则此次
比较结束，继续将模式串的第一位去与主串的下一位进行比较。由此看来，在模式串的第五
位上，进行的比较偏移了4位（不进行偏移，直接比较下一位为0），故第五位b的nextval
值为4。
我们可以利用第一个例子“abaabcac”对这种方法进行验证。
a的nextval值为0，因为如果主串的第一位不是a，那么没有再比较下去的必要，
直接比较主串的第二位是否为a。如果比较到主串的第二位才发生错误，则主串第一位肯定
为a，第二位肯定不为b，此时不能直接跳到第三位进行比较，因为第二位还可能是a，所
以对主串的第二位再进行一次比较，偏移了1位，故模式串第二位的nextval值为1。以此
类推，nextval值分别为：01021302。其中第六位的nextval之所以为3，是因为，如果主串
比较到第六位才发生不匹配现象，那么主串的前五位必定为“abaab”且第六位必定不是“c”，
但第六位如果为“a”的话，那么我们就可以从模式串的第四位继续比较下去。所以，这次
比较为： 1 2 3 4 5 6 7 8 9 10 11 12
a b a a b * * * * * * *
a b a a b c a c
而不是： 1 2 3 4 5 6 7 8 9 10 11 12
a b a a b * * * * * * *
a b a a b c a
因为前两位a和b已经确定了，所以不需要再进行比较了。所以模式串第六位的
nextval值为这次比较的偏移量3。
再来看求nextval数组值的第二种方法。
模式串 a b a a b c a c
next值 0 1 1 2 2 3 1 2
nextval值 0 1 0 2 1 3 0 2
1.第一位的nextval值必定为0，第二位如果于第一位相同则为0，如果不同则为1。
2.第三位的next值为1，那么将第三位和第一位进行比较，均为a，相同，则，第三
位的nextval值为0。
3.第四位的next值为2，那么将第四位和第二位进行比较，不同，则第四位的nextval
值为其next值，为2。
4.第五位的next值为2，那么将第五位和第二位进行比较，相同，第二位的next值
为1，则继续将第二位与第一位进行比较，不同，则第五位的nextval值为第二位的next值，
为1。
5.第六位的next值为3，那么将第六位和第三位进行比较，不同，则第六位的nextval
值为其next值，为3。
6.第七位的next值为1，那么将第七位和第一位进行比较，相同，则第七位的nextval
值为0。
7.第八位的next值为2，那么将第八位和第二位进行比较，不同，则第八位的nextval
值为其next值，为2。
在“aaaab”内进行验证。 模式串 a a a a b
next值 0 1 2 3 4
nextval值 0 0 0 0 4
