数据结构PPT教学课件-第4章_串.ppt

第四章 串,4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串操作应用举例,计算机上的非数值处理的对象基本上是字符串数据； 字符串一般简称为串； 现在我们使用的计算机硬件结构主要是反映数值计算的需要的，因此，在处理字符串数据时比处理整数和浮点数要复杂得多； 首要工作是根据具体情况使用更合适的存储结构。,串的特性,串的特性,串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。 然而，串的基本操作与线性表有很大差别。 在线性表的基本操作中，大多以“单个元素”作为操作对象，如：在线性表中查找某个元素、获取某个元素、在某个位置上插入一个元素和删除一个元素等； 而在串的基本操作中，通常以“串的整体”作为操作对象，如：在串中查找某个子串、获取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。,4.1 串类型的定义,串(string)是零个或多个字符组成的有限序列； 一般记作s=“a1a2a3an”，其中s是串名，双引号括起来的字符序列是串值； ai(1in)可以是字母、数字或其它字符； 串中所包含的字符个数称为该串的长度。长度为零的串称为空串(empty string)，它不包含任何字符。,通常将仅由一个或多个空格组成的串称为空白串(blank string)； 注意：空串和空白串的不同，例如“ ”和“”分别表示长度为1的空白串和长度为0的空串。,串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。 通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。,例如：设a和b分别为a=“this is a string” b=“is”则b是a的子串，a为主串。b在a中出现了两次，其中首次出现所对应的主串位置是3。因此，称b在a中的序号（或位置）为3。 特别地，空串是任意串的子串，任意串是其自身的子串。,通常在程序中使用的串可分为两种：串变量和串常量： 串常量和整常数、实常数一样，在程序中只能被引用但不能改变其值，即只能读不能写。 通常串常量是由直接量来表示的，例如语句error(“overflow”)中“overflow”是直接量； 但有的语言允许对串常量命名，以使程序易读、易写。如c+中，可定义 const char path=“dir/bin/appl”; 这里path是一个串常量，对它只能读不能写。,串变量和其它类型的变量一样，其取值是可以改变的。 另外值得一提的是，串值必须用一对单引号括起来，但单引号本身不属于串，它的作用只是为了避免与变量名或数的常量混淆而已。 例如：程序设计语言中 x=123；则表明x是一个串变量名，赋给它的值是字符序列123。,在各种应用中，空格常常是串的字符集合中的一个元素，因而可以出现在其它字符中间。由一个或多个空格组成的串一称为空格串（空白串，blank string），它的长度为串中空格字符的个数。 为了区别于空白串，用符号“”来表示“空串”。,串的抽象数据定义,串的抽象数据类型定义： 数据对象： d= ai|aielemset，i=1,2,n, n0 数据关系： r1= | ai-1， ai d，i=2,n 基本操作： strassign(&t, chars) 初始条件：chars是字符串常量。 操作结果：对一个空串t赋值。 strcopy(&t, s) 初始条件：串s存在。 操作结果：由串s复制得串t。,strempty(s) 初始条件：串s存在。 操作结果：若s为空串，则返回true， 否则返回false。 strcompare(s, t) 初始条件：串s和t存在。 操作结果：若st，则返回值0；若s=t， 则返回值=0；若st，则返回值0。 strlength(s) 初始条件：串s存在。 操作结果：返回s的元素个数，称为串的长度。,clearstring(&s) 初始条件：串s存在。 操作结果：将s清为空串。 concat(&t, s1, s2) 初始条件：串s1和s2存在。 操作结果：用t返回由s1和s2联接而成的新串。 substring(&sub, s, pos, len) 初始条件：串s存在，1posstrlength(s) 且0lenstrlength(s)-pos-1。 操作结果：用sub返回串s的第pos个字符起长度为len的子串。,index(s,t,pos) 初始条件：串s和t存在，t是非空串，1posstrlength(s)。 操作结果：若主串s中存在与串t值相同的子串，则返回它在主串s中第pos个字符之后第一次出现的位置；否则函数值为0。 replace(&s,t,v) 初始条件：串s、t和v存在，t是非空串。 操作结果：用v替换主串s中出现的所有与t相等的不重叠的子串,strinsert(&s, pos,t) 初始条件：串s和t存在，1posstrlength(s)+1。 操作结果：在串s的第pos个字符之前插入串t。 strdelete(&s, pos, len) 初始条件：串s存在，1posstrlength(s)-len+1。 操作结果：从串s中删除第pos个字符起长度为len的子串。 destroystring(&s) 初始条件：串s存在。 操作结果：串s被销毁。,补充说明,对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。 在上述抽象数据类型定义的13种操作中，串赋值 strassign、串比较strcompare、求串长strlength、串联接concat以及求子串substring等5种操作构成串类型的最小操作子集。 即：这些操作不可能利用其他串操作来实现； 反之，其他串操作（除串清除clearstring和串销毁destroystring外）均可在这个最小操作子集上实现。,对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现。下面介绍几种在c语言中常用的串运算: 定义下列几个变量： char s120=“dirtreeformat”, s220=“file.mem”; char s330, *p; int result;,串的基本操作,求串长(length) int strlen(char s); /求串的长度 例如：printf(“%d”,strlen(s1); 输出13 串复制(copy) char *strcpy(char to, char from); 该函数将串from复制到串to中，并且返回一个指向串to的开始处的指针。 例如：strcpy(s3,s1); /s3=“dirtreeformat”,char s120=“dirtreeformat”, s220=“file.mem”; char s330, *p; int result;,联接(concatenation) char * strcat(char to, char from) 该函数将串from复制到串to的末尾，并且返回一个指向串to的开始处的指针。 例如：strcat(s3,”/”) strcat(s3,s2); /s3=“dirtreeformat/file.mem”,char s120=“dirtreeformat”, s220=“file.mem”; char s330, *p; int result;,串比较（compare) int strcmp(chars1,char s2); 该函数比较串s1和串s2的大小，当返回值小于0，等于0或大于0时分别表示s1s2。 例如：result=strcmp(“baker”, ”baker”) result0 result=strcmp(“12”, ”12”); result=0 result=strcmp(“joe”, ”joseph”); result0,char s120=“dirtreeformat”, s220=“file.mem”; char s330, *p; int result;,字符定位(index) char * strchr(char s, char c); 该函数是找c在字符串中第一次出现的位置，若找到则返回该位置，否则返回null。 例如：p=strchr(s2,”.”); /p指向“file”之后的位置 if(p) strcpy(p,”.cpp”); /s2=“file.cpp”,char s120=“dirtreeformat”, s220=“file.mem”; char s330, *p; int result;,串的其余操作可由这些基本操作组合而成。 例1、求子串 求子串的过程即为复制字符序列的过程，将串s中的第pos个字符开始长度为len的字符复制到串t中。 void substr(string sub, string s, int pos, int len) if(posstrlen(s)-1 | len0) /参数pos和len的合法性判断 error(“parameter error”) strncpy(sub, /将串s中从第pos个字符开始取值，共取len个字符，将这些字符组成的串赋给sub ,例2、串的定位index(s,t,pos) 在主串中取从第i个字符起、长度和串t相等的子串和t比较，若相等，则求得函数值为i，否则值增1直至s中不存在和串t相等的子串为止。 int index(string s, string t, int pos) if(pos0) /pos的合法性判断 n=strlen(s); m=strlen(t); i=pos; while(in-m+1) /作为起始字符位的取值范围 substr(sub, s, i, m); /从串s取一段赋给sub if(strcmp(sub,t)!=0) /sub和t比较直到相等 +i; else return(i); /若相等，则返回函数值i return(0); /否则返回0 ,算法4.1,串基本操作演示,4.2 串的表示和实现,因为串是特殊的线性表，故其存储结构与线性表的存储结构类似。只不过由于组成串的结点是单个字符。串有三种表示方法。,定长顺序存储表示（静态存储分配的顺应表）：是用一组连续的存储单元来存放串中的字符序列。 所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先给出： #define maxstrlen 255 typedef unsigned char sstringmaxstrlen+1; /0号单元存串长,4.2.1 定长顺序存储表示,类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。 在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量预先分配一个固定长度的存储区域，可用定长数组描述，属于一种静态分配方式。例如：,实际串长可在所分配的固定长度区域内变动，超过于定义长度的串值则被舍去，称之为“截断”。,#define maxstrlen 255 /用户可在255以内定义最大串长 typedef unsigned char sstringmaxstrlen+1; /0号单元存放串的长度，字符从1号单元开始存放 sstring s; /s是一个可容纳255个字符的顺序串,对串长有两种表示方法： 一是以下标为0的数组分量存放串的实际长度，如pascal语言中的串类型采用这种表示方法； 二是在串值后面加一个不计入串长的结束标记字符，如在c语言中以“0”表示串值的终结。此时的串长为隐含值，但是这样不便于进行某些串操作。如，字符串student在c语言中的存储结构。,这就是为什么在上述定义中，串空间最大值maxstrlen为256，但最多只能存放255个字符的原因，因为必须留一个字节来存放0字符。,如何在这种存储结构表示时实现串的操作，例如串联接和求子串。 （1）串联接concat(&t,s1,s2) 假设s1、s2和t都是sstring型的串变量，且串t是由串s1联结串s2得到的； 即串t的值的前一段和串s1的值相等； 串t的值的后一段和串s2的值相等，则只要进行相应的“串值复制”操作即可。 只是需按约定，对超过部分实施“截断”操作。,基于串s1和s2长度的不同情况，串t值的产生可能有如下三种情况： 1）s10+s20maxstrlen，得到的串t是正确的结果； 2）s10maxstrlen，则将串s2的一部分截断，得到的串t只包含串s2的一个子串； 3）s10=maxstrlen，则得到的串t并非联接结果，而与串s1相等。,s10,s20,t0,maxstrlen,串的连接操作concat示意图 (a)s10+s20= maxstrlen,s10,s20,t0,maxstrlen,s2中被截去的字符序列,串的连接操作concat示意图 (b)s10 maxstrlen,s10,s20,maxstrlen,t0,s2串被全部截去,串的连接操作concat示意图 (c)s10=maxstrlen,串连接（算法4.2） status concat(sstring ,else t0maxstrlen=s10maxstrlen; uncut=false; return uncut; /concat,此时顺序串的类型定义和顺序表类似： typedef struct char chmaxstrlen; int length; sstring; /其优点是涉及到串长操作时速度快。,（2）求子串,求子串的过程即为复制字符序列的过程，将串s中从第pos个字符开始长度为len的字符序列复制到串sub中。 显然，本操作不会有要截断的情况，但有可能产生用户给出的参数不符合操作的初始条件，当参数非法时，返回error。,此时顺序串的类型定义和顺序表类似： typedef struct char chmaxstrlen; int length; sstring; /其优点是涉及到串长操作时速度快。,求子串（算法4.3） status substring (sstring /substring 使用顺序存储结构过程中可能出现串长度超过数组上限，经过截断的串已经不完整，克服这个问题可使用动态分配串值的存储空间。,综上两个操作可见，在顺序存储结构中，实现串操作的原操作为“字符序列的复制”，操作的时间复杂度基于复制的字符序列的长度。 另一操作特点是，如果在操作中出现串值序列的长度超过上界maxstrlen时，约定用截尾法处理，这种情况不仅在求联接串时可能发生，在串的其它操作中，如插入、置换等也可能发生。克服这个弊病只有不限定串长的最大长度，即动态分配串值的存储空间。,4.2.2 堆分配存储表示,这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表。 在c语言中，利用动态存储管理函数malloc()和free()，来根据实际需要动态分配和释放字符数组空间。 利用函数malloc()为每个新产生的串分配一块实际串长所需的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基址，同时，为了以后处理方便，约定串长也作为存储结构的一部分。,这样定义的顺序串类型也有两种形式： typedef char *string; /c中的串库相当于此类型定义 或者增加一个串长度信息项： typedef struct char *ch; int length; hsring;,这种存储结构表示时的串操作仍是基于“字符序列的复制” 。例如，串复制操作strcopy(&t, s)的实现算法是，若串t已存在，则先释放串t所占空间，当串s不空时，首先为串t分配大小和串s长度相等的存储空间，然后将串s的值复制到串t中。 又如，串插入操作strinsert(&s,pos,t)的实现算法是，为串s重新分配大小等于串s和串t长度之和的存储空间，然后进行串值复制。,status sinsert(hstring s, int pos, hstring t) /串插入操作 if(poss.length+1) /t插入s的位置的合法性判断 return error; if(t.length) if(!(s.ch=(char*)realloc(s.ch,(s.length+t.length)*sizeof(char) exit(overflow); /向系统要求合适的串空间 for(i=s.length-1;ipos-1;-i) /将串s中第pos位之后字符后移 s.chi+t.length=s.chi; s.chpos-1pos+t.length-2=t.ch0t.length-1; /串插入 s.length+=t.length; /串s的实际长度增加了t.length return ok; /插入成功，返回成功标志ok 算法4.4,求串长 int strlen(hstring s) return s.length; /返回串中实际字符个数，即长度 清空串 status clearstring(hstring s) if(s.ch) free(s.ch); s.ch=null; s.length=0; /释放串的存储空间，同时长度变为0 ,status strassign(hstring t, char *chars) /生成一个其值等于串常量chars的串t if(t.ch) free(t.ch); /先将串t清空 for(i=0; (c=chars; c; +i); +c); /计算串常量chars中字符个数 if(!i) t.ch=null; t.length=0; else if(!(t.ch=(char *)malloc(i*sizeof(char) exit(overflow); t.ch0i-1=chars0i-1; t.length=i; ,比较两个串的大小 int strcmp(hstring s,hstring t) for(i=0; is.length /所有字符相同时则比较长度 ,串联接 status concat(hstring t, hstring s1, hstring s2) if(!(t.ch)=(char*)malloc(s1.length+s2.length)*sizeof(char) /向系统申请合适的串空间 exit(overflow); /否则向系统报错 t.ch0s1.length-1=s1.ch0s1.length-1; t.length=s1.length+s2.length; t.chs1.lengtht.length-1=s2.ch0s2.length-1; /生成新串t，由串s1和串s2前后联接生成,status substr(hstring sub, hstring s, int pos, int len) /取子串 if(poss.length | lens.length-pos+1) return error; /判断位置pos的合法性，否则系统报错 if(sub.ch) free(sub.ch); /如果sub不是空串，则清空 if(!len) /如果要求取的子串的长度为0 sub.ch=null; sub.length=0; else sub.ch=(char *)malloc(len*sizeof(char); /要求子串空间 sub.ch0len-1=spos-1pos+len-2; s.length=len; ,4.2.3 串的块链存储表示,与线性表的链式存储结构相似，也可以采用链表方式存储串值。 由于串的数据元素是一个字符，它只有8位二进制， 因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串，例如：在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即：同一行的串用定长结构（80个字符），行和行之间用指针相联接。 由于串结构的特殊性结构中的每个数据元素是一个字符，当用链表存储串值时，存在一个“结点大小”的问题，即每个结点可以存放一个字符，也可以存放多个字符。,4.2.3 串的块链存储表示 用链表存储串，每个结点存储串的n个字符，当串长不是n的整数倍时最后一个结点剩余位置用空字符补齐。 如串abcdefghi当n=4时： 当n=1时：,a b c d,e f g h,i # # # ,head,a,b,c,i ,head,最直接的链式存储结构是每个结点的数据域存放一个字符，优点是操作方便；不足之处是存储密度较低。,用单链表方式来存储串值，称串的这种链式存储结构简为链串。 typedef struct node char data; struct node *next; lstring; 一个链串由头指针唯一确定，这种结构便于进行插入和删除运算，但存储空间利用率太低。,存储密度 = 串值所占的存储单元 / 实际分配的存储单元,为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点大小。 显然，当结点大小大于1时，串的长度不一定正好是结点的整数倍，则链表中的最后一个结点不一定全被串值占满，此时通常补上“#”或其它的非串值字符（一般情况下“#”不属于串的字符集，是一个特殊的符号）。,这种存储形式优点是存储密度高于结点大小为1 的存储形式。不足之处是做插入、删除字符的操作时，可能会引起结点之间字符的移动，算法实现起来比较复杂。,4.3 串的模式匹配算法,基本概念：子串定位运算又称为模式匹配（pattern matching）或串匹配（string matching）。 该运算的应用非常广泛。例如，在文本编辑程序中，经常要查找某一特定单词在文本中出现的位置。显然，处理此问题的有效算法能极大地提高文本编辑程序的响应性能。,1、穷举法（朴素）模式匹配,算法思想：从主串的指定位置开始，将主串与模式（要查找的子串）的第一个字符比较： 1、若相等，则继续逐个比较后续字符； 2、若不等，从主串的下一个字符起再重新与模式的字符比较。 设s=s1,s2,sn（主串），p=p1,p2,pm（模式串），i为指向s中字符的指针，j为指向p中字符的指针。 若(si-j+1 si-1)=(p1 pj-1) ，当sipj时，匹配失败。 失败匹配后需回溯： i=i-j+2 ； j=1 缺点：重复回溯太多。,穷举模式的匹配过程,第1趟 s a b b a b a p a b a,第2趟 s a b b a b a p a b a,第3趟 s a b b a b a p a b a,第4趟 s a b b a b a p a b a,匹配成功！,int index(sstring s, sstring t, int pos) /s为主串，t为模式，串的第0位置存放串长度；串采用顺序存储结构 i = pos; j = 1; / 从第一个位置开始比较 while (i t0) return i-t0; / 返回与模式第一字符相等的字符在主串中的序号 else return 0; / 匹配不成功 /index 算法4.1,算法效率分析,在最好的情况下，除比较成功的位置外，其余位置仅需比较一次（模式第一个字符），其时间复杂度为：o(n+m)（n、m分别为主串和模式的长度）。 例如：,主串： a b c d e f g h i j k l m n 模式： l m n,算法效率分析,在最坏的情况下，如模式为00000001，主串为0000000000000000000000000000000001，则每次模式的前7个0都要与主串逐一比较，因此，其时间复杂度为：o(n*m)。,朴素的模式匹配演示,a c a b a a b a a b c a c a a b c,a b a a b c,主串,模式,| | | | | |,a b a a b c,a b a a b c,a b a a b c,这趟匹配可以让模式的前缀与下划线串的后缀先进行，因为下划线字串表示当前段主串内容,匹配成功的串是这一段主串的内容,如果匹配可能成功，模式的某个前缀与上次匹配成功的某个后缀相等，否则，这趟匹配没必要。,2、kmp算法,是index函数的一种改进，由d.e.knuth（克努特）j.h.morris（莫里斯）v.r.pratt（普拉特）发现。 当一趟匹配过程中出现字符不等（失配）时： 1、不需回溯主串的i指针； 2、利用已经得到的“部分匹配”的结果，将模式向右“滑动”适当距离（nextj）后，继续进行比较。 3、这个距离可以从模式中预先计算出来。 4、提高匹配效率o(n)。,设主串ababcabcacbab，模式abcac， kmp算法的匹配过程如下： i=3 第一趟匹配： a b a b c a b c a c b a b a b c j=3 i=3-7 第二趟匹配： a b a b c a b c a c b a b a b c a c j=1 i=7-10 第三趟匹配： a b a b c a b c a c b a b a b c a c j=2,s s1 s2 si+1 si+2 si+3 si+j-1 si+j si+j+1 sn p p1 p2 p3 . pj-1 pj pj+1 则有：si+1 si+2 si+3 si+j-1 = p1 p2 p3 pj-1 为使模式 p 与目标 s 匹配，必须满足： p1 p2 pj-1 pjpm = si-j+1 si-j+2 si-1 si si-j+m 如果： p1 p2 pj-2 p2 p3 pj-1 ，则立刻可以断定： p1 p2 pj-2 si+2 si+3 si+j-1，即便下一趟右移一位也必不匹配。,p1 p2 pj-2 pj-1 ,s s1 s2 si+1 si+2 si+3 si+j-1 si+j ss+j+1 sn p p1 p2 p3 pj-1 pj pj+1 同样，若： p1 p2 pj-3 p3 p4 pj-1 则再下一趟也不匹配，因为有： p1 p2 pj-3 si+3 si+4 si+j-1,p1 p2pj-3 pj-2 ,直到对于某一个“k”值，使得 p1 p2 pk pj-k pj-k+1 pj-1 且 p1 p2 pk-1 = pj-k+1 pj-k+2 pj-1 则 p1 p2 pk-1 = si+j-k+1 si+j-k+2 si+j-1,s s1 s2 si+1 si+j-k+1 si+j-1 si+j si+j+1 sn p p1 pj-k+1 pj-1 pj pj+1 ,p1 pk-1 pk , ,s s1 si+1 si+2 si+j-k+1 si+j-1 si+j sn p p1 p2 pj-k+1 pj-1 pj | | p1 pk-1 pk pj+1,主串指针不动,模式指针从pk开始比较,下一趟匹配,假设主串为s1s2s3sn，模式串为p1p2p3pm，若主串中第i个字符与模式串中第j个字符“失配”（sipj），需要与模式串中第k（kj）个字符比较，则有以下关系成立： p1p2pk-1 = si-k+1si-k+2si-1 而已经得到的“部分匹配”结果为： pj-k+1pj-k+2pj-1 = si-k+1si-k+2si-1 从而成立：p1p2pk-1 = pj-k+1pj-k+2pj-1,s s1 si-j+1 si-j+2 si-k+1 si-1 si sn p p1 p2 pj-k+1 pj-1 pj | | p1 pk-1 pk pj+1,上式是只依赖于模式串本身的关系式。说明：在主串中第i个字符“失配”时，仅需与模式串中的第k个字符再开始比较（不需要回溯）。 或者换言之，在模式串中第j个字符“失配”时，模式串第k个字符再同主串中对应的失配位置(i)的字符继续进行比较： p1p2pk-1 = pj-k+1pj-k+2pj-1 k值可以在作串的匹配之前求出，一般用next函数求取k值。,s s1 si-j+1 si-j+2 si-k+1 si-1 si sn p p1 p2 pj-k+1 pj-1 pj | | p1 pk-1 pk pj+1,next函数,用nextj表示k，它表示当比较到模式第j个字符失配时， 模式指针返回从 k开始匹配。k的值与模式的前 j-1个字符有关，与目标无关。next函数定义为：,p1p2pk-1 = pj-k+1pj-k+2pj-1,例如：k=2，则p1=pj-1，有1个字符相同，j=2除外 k=3，则p1p2=pj-2pj-1 ，有2个字符相同,next数组的求解方法是：第一位的next值为0，第二位的next值为1； 后面求解每一位的next值时，根据前一位进行比较，首先将前一位内容与其next值对应的内容进行比较： 如果相等，则该位的next值就是前一位的next值加上1； 如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值； 如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。,p1p2pk-1 = pj-k+1pj-k+2pj-1,举例：next函数值的求取,例如，求下列字符串的next数组值。 序号j 1 2 3 4 5 6 7 8 模式p a b a a b c a c k 1 1 2 2 3 1 2 pk=pj = = = nextj 0 1 1 2 2 3 1 2 nextvalj 0 1 0 2 1 3 0 2,1、前两位必定为0和1。 2、计算第三位的时候，看第二位b的next值，为1，则把b和1对应的a进行比较，不同，则第三位a的next的值为1，因为一直比到最前一位，都没有发生比较相同的现象。,序号j 1 2 3 4 5 6 7 8 模式p a b a a b c a c k 1 1 2 2 3 1 2 pk=pj = = = nextj 0 1 1 2 2 3 1 2 nextvalj 0 1 0 2 1 3 0 2,将前一位内容与其next值对应的内容进行比较： 如果相等，则该位的next值就是前一位的next值加上1； 如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值； 如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。,3、计算第四位的时候，看第三位a的next值，为1，则把a和1对应的a进行比较，相同，则第四位a的next的值为第三位a的next值加上1，为2。因为是在第三位实现了其next值对应的值与第三位的值相同。,序号j 1 2 3 4 5 6 7 8 模式p a b a a b c a c k 1 1 2 2 3 1 2 pk=pj = = = nextj 0 1 1 2 2 3 1 2 nextvalj 0 1 0 2 1 3 0 2,将前一位内容与其next值对应的内容进行比较： 如果相等，则该位的next值就是前一位的next值加上1； 如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值； 如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。,4、计算第五位的时候，看第四位a的next值，为2，则把a和2对应的b进行比较，不同，则再将b对应的next值1对应的a与第四位的a进行比较，相同，则第五位的next值为第二位b的next值加上1，为2。因为是在第二位实现了其next值对应的值与第四位的值相同。,序号j 1 2 3 4 5 6 7 8 模式p a b a a b c a c k 1 1 2 2 3 1 2 pk=pj = = = nextj 0 1 1 2 2 3 1 2 nextvalj 0 1 0 2 1 3 0 2,将前一位内容与其next值对应的内容进行比较： 如果相等，则该位的next值就是前一位的next值加上1； 如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值； 如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。,5、计算第六位的时候，看第五位b的next值，为2，则把b和2对应的b进行比较，相同，则第六位c的next值为第五位b的next值加上1，为3，因为是在第五位实现了其next值对应的值与第五位相同。,序号j 1 2 3 4 5 6 7 8 模式p a b a a b c a c k 1 1 2 2 3 1 2 pk=pj = = = nextj 0 1 1 2 2 3 1 2 nextvalj 0 1 0 2 1 3 0 2,将前一位内容与其next值对应的内容进行比较： 如果相等，则该位的next值就是前一位的next值加上1； 如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值； 如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。,6、计算第七位的时候，看第六位c的next值，为3，则把c和3对应的a进行比较，不同，则再把第3位a的next值1对应的a与第六位c比较，仍然不同，则第七位的next值为1。,序号j 1 2 3 4 5 6 7 8 模式p a b a a b c a c k 1 1 2 2 3 1 2 pk=pj = = = nextj 0 1 1 2 2 3 1 2 nextvalj 0 1 0 2 1 3 0 2,将前一位内容与其next值对应的内容进行比较： 如果相等，则该位的next值就是前一位的next值加上1； 如果不等，向前继续寻找next值对应的内容来与前一位进行比较，直到找到某个位上内容的next值对应的内容与前一位相等为止，则这个位对应的值加上1即为需求的next值； 如果找到第一位都没有找到与前一位相等的内容，那么需求的位上的next值即为1。,7、计算第八位的时候，看第七位a的next值，为1，则把a和1对应的a进行比较，相同，则第八位c的next值为第七位a的next值加上1，为2，因为是在第七位和实现了其next值对应的值与第七位相同。,序号j 1 2 3 4 5 6 7 8 模式p a b a a b c a c k 1 1 2 2 3 1 2 pk=pj = = = nextj 0 1 1 2 2 3 1 2