版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
4.1字符串的类型定义4.2字符串的表示和实现4.2.1串的顺序存储结构4.2.2串的链式存储结构4.3字符串的模式匹配4.4字符串的应用举例第四章字符串定义和概念字符串简称为串(String):由零个或多个字符组成的有限序列。记为:s=’a1a2…an’(n≥0)概念:s为串名‘a1a2…an’为串值例如:s=‘YantaiUniversity’n为串的长度ai
为串中字符,以ASCII形式存储n=0,空串(NullString),记为:Ф若ai
=‘’,则称为空格串(blankstring)字符串的抽象数据类型定义ADTSTRING{数据对象:D={ai
|ai
CharacterSet
,i=1,2,...,n,n>=0}
数据关系:R={<ai-1
,ai>|ai-1,ai
D,i=2,...,n}基本操作:串赋值:StringAssign(S,T)串复制:StringCopy(S,T)
求串长:StringLenth(S)
串判等:StringEqual(S,T)
串联接:StringConcat(S,T)
求子串:SubString(S,start,length)
初始条件:串s存在,1<=start<=Stringlength(s)+1,
且:0<=length<=Stringlength(s)-start+1
操作结果:返回主串s中以start为起始位置、长度等于length的子串}STRING这6个操作是串类型的最小操作子集子串的定义:串中任意连续的字符组成的子序列称为该串的子串Length可以为0,此时表示求的是空串。以S=’abcdefghij’为例,length=10,如果start=11,则这时就是求空串。若start=6,则0<=length<=10-6+1=5,及此时的length的最大值为5,从第6个字符开始到结束总共有5个字符字符串的抽象数据类型定义(续)子串定位:Index(S,T)(S是主串,T是模式串)扩展形式为:Index(S,T,pos)(pos=1时就是上述形式)初始条件:串S和T存在,T是非空串,
1≤pos≤StrLength(S)操作结果:若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置,否则函数值为0字符串的抽象数据类型定义(续)置换:Replace(S,T,V)
插入子串:StringInsert(S,start,T)
初始条件:串S和T存在,1<=start<=
Stringlength(s)+1
操作结果:在串S的第start个字符之前插入串T。删除子串:StringDelete(S,start,length)
初始条件:串S和T存在,1<=start<=
Stringlength(s)-length+1
操作结果:从串S中删除第start个字符起长度为length的子串。
长度分别为18、7、3、3;且b、c、d都是a的子串;b在a中的位置是1,c在a中的位置是12;c和d两串相等
例:a=’WelcometoBeijing’b=’Welcome’c=’Bei’d=’Bei’
表明可以插入在串S的最后串和线性表的比较串的逻辑结构和线性表极为相似,即都有位序的问题。区别仅在于串的数据对象约束为字符集。然而:串的基本操作和线性表有很大差别。在线性表的基本操作中,大多以“单个元素”作为操作对象,如:在线性表中查找某个元素、求取每个元素、在某个位置上插入、删除一个元素等;而在串的基本操作中,通常以“串的整体”作为操作对象,如:在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。关于串的操作对于串的基本操作集可以有不同的定义方法,读者在使用高级程序设计语言中的串类型时,应以该语言的参考手册为准。如在C语言中串赋值StrAssign、串复制StrCopy、串比较StrCompare、求串长StrLength、串联接StrConcat、求子串SubString等6种操作构成串类型的最小操作子集。即这些操作不可能利用其他串操作来实现。反之,其他串操作(除串清除ClearString和串销毁DestroyString外)均可在这个最小操作子集上实现。C语言中的串操作函数gets(string)输入一个字符串;puts(string)输出一个字符串;strcat(str1,str2)将两个串连接成一个新串strcpy(str1,str2)将字符串str2的值复制给str1变量strcmp(str1,str2)将两个字符串进行比较strlen(str)求字符串的长度strlwr(str)将字符串str中的大写字母换成小写字母strupr(str)将字符串str中的小写字母换成大写字母定位函数Index(S,T,pos)例如可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos)。算法的基本思想为:在主串S中取从第i(i的初值为pos)个字符起、长度和串T相等的子串和T比较,若相等,则求得函数值为i,否则i值增1直至串S中不存在和串T相等的子串为止。定位函数Index(S,T,pos)Strcompare(Substring(S,i,StrLength(T)),T)=0?可用下列算法实现int
Index(String
S,String
T,intpos){//T为非空串,若主串S中第pos个字符之后存在与T相等的子串,则返回第一个这样的子串在S中的位置,否则返回0if(pos>0){n=StrLength(S);m=StrLength(T);i=pos;
while(i<=n-m+1)//当i加上T的长度超过串S的长度时结束
{StringAssign(sub,SubString(S,i,m));∥在串s中从第i个字符开始取长度为m的字串
if(StrCompare(sub,T)!=0)++i;elsereturni;}//while}//ifreturn0;//S中不存在与T相等的子串}//Index教材P.68.算法4.1串的表示和实现如果在程序设计语言中,串只是作为输入或输出的常量出现,则只需存储此串的串值,即字符序列即可。但在多数非数值处理的程序中,串也以变量的形式出现,因此字符串也有存储映像的问题。串的表示和实现串有三种机内表示方法串的顺序存储结构:用一组连续的存储单元依次存储串中的字符序列。
1.定长顺序存储表示:事先定义字符串的最大长度2.“堆”分配存储表示:在程序执行过程中,利用标准函数malloc和free动态地分配或释放存储字符串的存储单元,并以一个特殊的字符(例如’\0’)作为字符串的结束标志链式表示3.块链存储表示静态的动态的串的顺序存储结构定长顺序存储表示:事先定义字符串的最大长度#defineMAX_STRING255∥用户可能达到的最大串长typedefunsignedcharSString[MAX_STRING+1];∥0号单元存放串的长度,字符从1号单元开始存放串的实际长度可在这个预定义长度的范围内随意设定,超过预定义长度的串值则被舍去。称之为“截断”设有两个字符串,分别为:‘data’和‘structures’,且假设strlen=10,则strconcat(‘data’,‘structures’)=‘datastruct’而strconcat(‘structures’,’data’)=‘structures’因此:串的联接算法中需分三种情况考虑:1).两串长度之和小于等于字符串最大长度:未截断;2).两串长度之和大于字符串最大长度:截断;3).第一字符串的长度大于字符串最大长度:截断,仅取第一字符串综上所述:对于定长顺序存储表示的字符串进行串的运算时,其基本操作为:‘字符序列的复制’串的顺序存储结构之“堆”分配存储表示“堆”分配存储表示:在程序执行过程中,利用标准函数malloc和free动态地分配或释放存储字符串的存储单元,并以一个特殊的字符(例如’\0’)作为字符串的结束标志.称串值共享的存储空间为“堆”typedef
struct{char*str;//若是非空串,则按串长分配存储区,否则str为NULL
intlength;//串长度}HString;注意由于在字符串操作中通常以“串的整体”作为操作对象,所以虽然是用malloc动态的分配存储,但是因为存储地址是连续的,也把它认为是顺序存储的。实际上,此处的str是一个字符串指针通常,C语言中通过的串类型就是以这种存储方式实现的,系统利用函数malloc()和free()进行串值空间的动态管理,为每一个新产生的串分配一个存储区,称串值共享的存储空间为“堆”,C语言的串以一个空字符‘\0’为结束符,串长是一个隐含值。这类串操作的实现算法为:先为新生成的串分配一个存储空间,然后进行串值的复制。基本操作:串的赋值int
StringAssign(HString*S,HString*T){∥将串T的值赋给串Sif(S->str)free(S->str);∥若s已经存在,将它占据的空间释放掉
len=T->length;∥T串的长度
S->length=len;∥赋予字符串长度
if(!len)∥空串
{S->str=(char*)malloc(sizeof(char));S->str[0]=’\0’;//串结束标志,‘\0’是人为的加上去的
}else∥非空串
{S->str=(char*)malloc((len+1)*sizeof(char));∥分配空间
if(!S->str)returnERROR;for(i=0;i<=len;i++)∥对应的字符赋值
S->str[i]=T->str[i];}∥ifreturnOK;}∥StringAssign
上述第二种方式定义下串不可以整体赋值,需要每个字符实现复制多余的1个存放‘\0’教材P.69.算法4.2
基本操作:串联接int
StringConcat(HString*S,HString
*T){∥将串T联接到串S后
HStringtemp;
StringAssign(&temp,S);∥将S原来的内容保留在temp中
S->length=S->length+T->length;∥计算S和T的长度之和为S的新长度
free(S->str);∥释放S原来占据的空间
S->str=(char*)malloc((s->len+1)*sizeof(char));∥重新为S分配空间
if(!s->str)returnERROR;else{∥连接两个串的内容
for(i=0;i<temp.length;i++)∥将temp的值先赋给SS->str[i]=temp.str[i];for(j=0;j<=T->length;j++,i++)∥将T的值赋在S现有值之后
S->str[i]=T->str[j];
free(temp.str);∥释放为临时串temp分配的空间
returnOK;}∥if}∥StringConcat
注意一个是<,一个是<=,为什么?即第二个for把串T的最后一个‘\0’也复制过去了。因为temp是一个变量,所以用temp.length,而S是指针变量,所以用S->str[i]教材P.70.算法4.3int
Index(HString*S,HString*T){∥返回子串T在主串S中的位置,若T非S的子串返回0i=0;j=0;∥设置两个扫描指针
while(i<S->length&&j<T->length){if(S->str[i]==T->str[j]){i++;j++;}else∥对应字符不相等时,重新比较
{i=i-j+1;j=0;}∥if}∥whileif(j==T->length)returni-T->length+1;∥返回子串在主串中的位置
elsereturn0;}∥Index
基本操作的算法:子串定位注意第二种顺序存储表示时从0号开始存放教材P.70.算法4.4定长顺序表示中的C表示方法在C中,字符串的概念是:以‘\0’为结尾的字符数组。初始化:Strings;S[0]=‘\0’;串的链式存储结构串作为一种特殊的线性表(数据元素为字符),使用顺序表示时,做插入和删除运算,运算量很大,不方便。链式存储结构:string
^S直接使用线性链表来存储字符串:效率太低实际分配的存储单元串值所占的存储单元存储密度=
串的块链存储结构#defineCHUNKSIZE80∥可由用户定义的块大小typedef
struct
Chunknode{∥结点结构
charch[CHUNKSIZE];//每个结点放一个串,如文本的一行
struct
Chunknode*next;}Chunk;typedef
struct
{∥串的链表结构
Chunk*head,*tail;∥串的头和尾指针
int
curlen;∥串的当前长度
}LString;
Sstring####^块链式结构的定义注意教材P.71.的结点定义错误块链式存储结构的优点是存储密度高,缺点是做插入/删除等操作时可能会引起结点之间字符的移动,算法实现比较复杂这种结构下处理文本时,每行是一个结点,行与行之间用指针相连接关于串的块链存储结构串值也可以用链表来存储,由于串的数据元素是一个字符,它只有8位二进制数,因此用链表存储时,通常一个结点中存放的不是一个字符,而是一个子串,例如,在文本编辑系统中,整个文本编辑区可以看成是一个串,每一行是一个子串,构成一个结点。即同一行的串用定长结构(80个字符),行和行之间用指针相联接。文本编辑时插入或删除一行很方便,不影响别的行。块链运算:插入Hesi
sdenuta##.t٨Heisastudent.Heisabrightstudent.串链表结构的尾指针串链表结构的头指针curlen串链表结构的头结点块链运算:插入Hesi
bgenira##.t٨httus
d#####尾指针不变curlen练习题:选择若串S=’software’,其子串的数目是()。【西安电子科技大学2001应用一、2(2分)】A.8B.37C.36D.9答案为:B实际上为:8+7+6+5+4+3+2+1+1=37即是取1个字符的组合、取2个字符的组合、……一直到取8个字符的组合(串本身可以认为是其自身的字串),还包括空串也是子串。选择设S为一个长度为n的字符串,其中的字符各不相同,则S中的互异的非平凡子串(非空且不同于S本身)的个数为()。【中科院计算所1997】A.2n-1B.n2
C.(n2/2)+(n/2)D.(n2/2)+(n/2)-1E.(n2/2)-(n/2)-1F.其他情况答案为:D此题出的比前一道题好,无有关子串的二义性问题选择串的长度是指()【北京工商大学2001一、6(3分)】A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数答案为:B填空串是一种特殊的线性表,其特殊性表现在__(1)__;串的两种最基本的存储方式是__(2)__、__(3)__;两个串相等的充分必要条件是__(4)__。【中国矿业大学2000一、3(4分)】(1):其数据元素都是字符(2):顺序存储(3):链式存储(4):串的长度相等且两串中对应位置的字符也相等4.3字符串的模式匹配(子串定位)这是串的一种重要操作,很多软件,若有“编辑”菜单项的话,则其中必有“查找”子菜单项。4.3字符串的模式匹配(子串定位)首先回忆一下串匹配(查找)的定义:Index(S,T,pos)(S是主串,T是模式串)初始条件:串S和T存在,T是非空串,
1≤pos≤StrLength(S)操作结果:若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置,否则函数值为0。4.3字符串的模式匹配(子串定位)方法1:朴素的模式匹配算法(简单算法)(Brute-Force算法即BF算法);方法2:首尾模式匹配算法;方法3:KMP算法;以下的讨论采用定长顺序存储结构#defineMAX_STRING255∥用户可能达到的最大串长typedefunsignedcharSString[MAX_STRING+1];∥0号单元存放串的长度,字符从1号单元开始存放朴素的串的模式匹配子串定位算法Index基本思想:先以主串S中第一个字符为S子串的头一个字符,截取模式串T的长度的子串,然后与模式串T中的字符逐个比较,若子串与模式串相同,即返回S子串的头一个字符位置作为查找的位置;否则,取S中第二个字符为子串头,将其往后的字符再依次与模式串T比较判断是否相等,以此类推直到找到位置或未有一个子串与模式串相同为止。
朴素的模式匹配主串S=’ababcabcacbab’,模式串T=‘abcac’
↓i=3第一趟匹配:ababcabcacbab
abc↑j=3↓i=2第二趟匹配:ababcabcacbab
a↑j=1
↓i=7第三趟匹配:ababcabcacbab
abcac↑j=5
↓i=4第四趟匹配:ababcabcacbab
a↑j=1
↓i=5第五趟匹配:ababcabcacbab
a↑j=1
↓i=11第六趟匹配:ababcabcacbab
abcac↑j=6该算法存在着指针的“回溯”,回溯次数越多,效率越低。如:S=000000000000001T=00001算法的时间复杂度为O(n*m)朴素的模式匹配算法int
Index(SStringS,T){∥返回子串T在主串S中的位置,若T非S的子串返回0i=1;j=1;∥设置两个扫描指针
while(i<=S[0]&&j<=T[0]){if(S[i]==T[j]){i++;j++;}//继续比较后续字符
else∥对应字符不相等时,指针后退重新开始匹配
{i=i-j+2;
j=1;}∥if}∥whileif(j>T[0])returni-T[0];∥返回子串在主串中的位置
elsereturn0;}∥Index
i=8S=‘dfnamrujhzasnamruot’T=‘namruo’j=6改进算法之:首尾模式匹配算法基本思想:
先比较模式串的第一个字符,
再比较模式串的最后一个字符,
最后比较模式串中从第二个到第n-1个字符。
改进算法之:首尾模式匹配算法基本思想:先比较模式串的第一个字符,再比较模式串的最后一个字符,最后比较模式串中从第二个到第n-1个字符。
主串:ababcabcaaabcbaabc模式串:aa(2次)
aaa(1+2次)aaabcba(2+5次)aaaa(2+2次)aa(2次)abcba(5次)例如主串S=’ababcabcaaabcbaabc’,模式串T为’abcba’
当首尾相等时,从模式串的第2个字符起依次第3个第4个,……,一直比较到模式串的倒数第2个为止首尾模式匹配算法int
Index_FL(SStringS,T){∥返回子串T在主串S中的位置。若不存在,则函数值
//为0。其中,T非空。
sLength=S[0];
tLength=T[0];i=1;
patStartChar=T[1];//模式串的第一个字符
patEndChar=T[tLength];∥模式串的最后一个字符
首尾模式匹配算法(续)while(i<=sLength–tLength+1)
{if(S[i]!=patStartChar)++i;∥重新查找匹配起始点
elseif(S[i+tLength-1]!=patEndChar)++i;∥模式串的“尾字符”不匹配,重新查找匹配起始点
else{
∥检查从第2个字符起的中间字符的匹配情况
k=1;j=2;while(j<tLength&&S[i+k]==T->str[j]){++k;++j;}∥while
if(j==tLength)returni;
else++i;
∥重新开始下一次的匹配检测
}∥else
}∥whilereturn0;}∥Index_FL首尾模式匹配算法减少了一定量的比较,但是并未真正的消除回溯当首尾相等时,从模式串的第2个字符起依次第3个第4个,……,一直比较到模式串的倒数第2个为止改进方法之:KMP算法特点
无需回溯在O(n+m)的时间量级上完成串的模式匹配操作
三个人的名字:D.K.KnuthV.R.PrattJ.H.Morris1.KMP算法
s=‘abbaba’t=‘aba’
∵t1=s1,t2=s2,t3≠s3又∵t1≠t2∴t1≠s2∴t右移一位后与s2(及b)的比较一定不等又∵
t1=t3∴
t1≠s3
∴t再右移一位后与s3(及b)的比较一定不等
因此:把t直接右移三位,及t1和s4直接比较即可。相对于s而言,消除了回溯。1.KMP算法(续)问题
substr(t,1,j-1)=substr(s,i-j+1,i-1)
tj
≠
si
时,确定t中哪个字符和si进行比较。把该字符记为tk,显然k<j.
对于不同的j,k值也不同。Knuth等人发现:此k值仅依赖于模式串t本身前j个字符的构成,而与s无关。用next[j]表示与j对应的k值。1.KMP算法(续)若next[j]>0:则tj
≠
si则用tk
=tnext[j]与si比较若next[j]=0:则tj
≠
si则用si+1与t1比较Ex:S=‘acabaabaabcacaabc’T=‘abaabc’next值:j123456模式串abaabcnext[j]011223Next[j]的意义是:
↓i=2第一趟匹配:主串acabaabaabcacaabc
模式串ab↑j=2next[2]=1↓i=2第二趟匹配:主串acabaabaabcacaabc
模式串a↑j=1next[1]=0
↓i=3→
↓i=8第三趟匹配:主串acabaabaabcacaabc
模式串abaabc↑j=1→
↑j=6next[6]=3↓i=8→
↓i=12第四趟匹配:主串acabaabaabcacaabc
模式串(ab)
aabc
↑j=3→
↑j=7
1.KMP算法(续)j123456模式串abaabcnext[j]0112231.KMP算法(续)int
Index_KMP(SStringS,T){//利用模式串T的next函数求T在主串S中的位置的KMP算法。
//其中,T非空
i=1;j=1;//初始化
while(i<=S[0]&&j<=T[0]){if(j==0||S[i]==T[j]){++i;++j;}∥继续比较后继字符
elsej=next[j];
∥模式串向右移动
}∥whileif(j>T[0])returni-T[0];∥匹配成功
elsereturn0;}∥Index_KMP
该算法的时间复杂度为O(n),n为主串s的长度请把该算法与朴素的模式匹配算法进行比较,观察相同和不同之处。差别仅在粉红色部分教材P.73.算法4.5略有不同2.如何求next[j]主串:模式串:当Si
≠Pj时,Si应与Pk(k<j)继续比较,此时必定有:(1)2.如何求next[j](续)已经得到的“部分匹配”结果是:
(2)由(1)式和(2)式可得:(3)2.如何求next[j](续)该(3)式说明:k的取值应使的k-1个字符组成的子串相等。即:substr(p,1,k-1)=substr(p,j-k+1,k-1)P右移j-k位后:?2.如何求next[j](续)可能有两种情况:1):若pk=pj,则表明即:next[j+1]=k+1,也就是说:next[j+1]=next[j]+12):若pk<>pj,则求next函数值的问题又是一个模式匹配的问题,只不过整个模式串既是主串又是模式串。2.如何求next[j](续)例:S=’abaabdabaabc’P=‘abaabc’i=6j=6s6≠p6,此时应该s6与p3比较,则:i=6,j=6,即k=3∴j123456模式串abaabcnext[j]0112232.如何求next[j](续)令next[j]=k,则next[j]表明:当si
≠tj时,在模式串t中需重新和主串中si
继续进行比较的字符的位置。所以next函数的定义如下:即集合为空时,即不存在一个满足:2.如何求next[j](续)j12345678模式串tabaabcacnext[j]
例如:01122312如何求next[j](续)
next数组的具体生成方法:
next数组的值完全取决于模式串t本身,而与目标主串无关,所以首先求出next数组的值:2.如何求next[j](续)
next数组的具体生成方法:实际上:求next函数值的运算实质上也是一个模式匹配的问题。若表明在第j+1个字符之前不存在长度为next[j]+1的和首字符起的子串模式相匹配的子串,然而是否有可能一个长度较短的可与首字符起的子串模式相匹配的子串呢?由kmp算法的启发:设next[j]=k’,则应将和相比较,若则说明在模式的第j+1个字符之前存在一个长度为next[k]+1且与首字符起的子串模式相匹配的子串。否则依次类推找更短的子串,直至不存在可匹配的子串,则next[j+1]=1。2.如何求next[j](续)
next数组的具体生成方法:如下图的模式中,已求得前6个字符的next函数值,现在求next[7]。∵next[6]=3,又∵则需比较
和(∵next[3]=1),这相当于将子串模式向右滑动。∵∴next[7]=1;∵则next[8]=next[7]+1=2
j123456
7
8模式串tabaabc
a
cnext[j]011223
1
22.如何求next[j](续)
next数组的具体生成方法:求next函数值的过程是一个递推过程,分析如下:
已知:next[1]=0;
假设:next[j]=k,又T[j]=T[k]
则:
next[j+1]=k+1
若:
T[j]≠T[k]
则需往前回溯,检查T[j]=T[?]
这实际上也是一个匹配的过程,不同在于:主串和模式串是同一个串。2.如何求next[j](续)求next数组的算法voidGet_Next(SStringT,intnext[]){//求模式串T的next函数值存入next数组中
i=1;next[1]=0;j=0;while(i<T[0]){if(j==0||T[i]==T[j]){++i;++j;
next[i]=j;}elsej=next[j];//j指针回溯
}//while}//Get_Next该算法的时间复杂度为O(m)。通常:模式串的长度m比主串的长度n要小很多,即:m<<n,所以增加这点时间是值得的Kmp算法的时间复杂度为O(m+n)与教材P.74.算法4.6略有不同2.如何求next[j](续)注意:满足(3)式的k可能有多个,此时应该选择其中最大的k,因为这样移动的次数(j-k)最少。以P=‘aaab’为例:当P4=b匹配不成功时,按照式(3),k可以取1、2或3(分别对应于右移3位、2位或1位),但只有取
k=3时,即右移j-k=4-3=1位时,才能保证不丢失任何匹配成功时的可能。2.如何求next[j](续)K=3,p右移一位:aaab
匹配成功
K=2,p右移二位:aaab
匹配不成功
K=1,p右移三位:aaab
匹配不成功此例中,p1p2=p2p3第四章练习已知串S=‘aaab’,其Next数组值为()。【西安电子科技大学1996一、7(2分)】A.0123B.1123C.1231D.1211答案为:A串‘ababaaababaa’的next数组为()。【中山大学1999一、7】A.012345678999B.012121111212C.011234223456D.012301232234答案为:C模式串P=‘abaabcac’的next函数值序列为________。【西安电子科技大学2001软件一、6(2分)】答案为:01122312模式串t=‘abcaabbcabcaabdab’,该模式串的next数组的值为()A.01112211123456712B.01112121123456112C.01110013101100701D.01112231123456712E.01100111011001701F.01102131011021701【北京邮电大学1998二、3(2分)】答案为:D设字符串S=‘aabaabaabaac',P=‘aabaac'(1)给出S和P的next值和nextval值;(2)若S作主串,P作模式串,试给出利用BF算法和KMP算法的匹配过程。【北方交通大学1998二(15分)】
S的next值为:012123456789P的next值为:012123改进的求next数组的算法事实上,上述的求next数组的算法有缺陷。如:S=‘aaabaaaab’T=‘aaaab’此时next数组的值为:则根据kmp算法,还需进行共三次比较。实际上因为t中的所以不需要再和s4进行比较,而可以将模式串一气向右滑动4个字符位置直接进行的比较,也就是说:若next[j]=k,而又有不需要再和tk进行比较,而直接和进行比较即可。换句话说:此时的
next[j]=next[k]j1
2
34
5模式串taaaabnext[j]012343.改进的求next数组的算法(续)voidGet_NextVal(SStringT,int
nextval[]){//求模式串T的next函数修正值存入nextval数组中
i=1;nextval[1]=0;j=0;while(i<T[0]){if(j==0||T[i]==T[j]){++i;++j;
if(T[i]!=T[j])nextval[i]=j;elsenextval[i]=nextval[j];}//if
elsej=nextval[j];}//while}//Get_NextVal与教材P.74.算法4.7略有不同3.改进的求next数组的算法(续)j模式串tnext[j]nextval[j]
12345aaaab
01234
00004关于串的匹配算法主要有四个:简单算法;KMP算法;NEXT函数值的求法;NEXTVAL函数值的求法;
这四个算法是相同的,当然有些区别。只要记住一个算法,其它算法就好理解了,当然要弄清楚NEXT函数值的意义字符串的应用文本编辑p.74.大致了解第四章总结1.
熟悉串的七种基本操作的定义,并能够利用这些基本操作来实现串的其它各种操作的方法;2.熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法;3.掌握串的堆存储结构以及在其上实现串操作的基本方法;4.理解串匹配的KMP算法,熟悉NEXT函数的定义,学会手工计算给定模式串的NEXT函数值和NEXTVAL函数值;5.理解串操作的应用方法;作业第四章4.1,4.2,4.4,4.5,4.6,4.9,4.104.12,4.14应用题试利用KMP算法和改进算法分别求p1=‘abaabaa’和p2=‘aabbaab’的next函数和nextval函数。【东南大学1999一、6(8分)】P1的next:0112234P1的nextval:0102102P2的next:0121123P1的nextval:0021002选择字符串‘ababaabab’的nextval
为()A.(0,1,0,1,0,4,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)答案为:ANext数组值为:011234234填空字符串’ababaaab’的nextval函数值为________。【北京邮电大学2001二、4(2分)】答案为:Nextval值为:01010421Next值为:01123422选择模式串t=‘abcaabbcabcaabdab’,该模式串的next数组的值为(),nextval数组的值为()。A.01112211123456712B.01112121123456112C.01110013101100701D.01112231123456712E.01100111011001701F.01102131011021701【北京邮电大学1998二、3(2分)】Next值为:DNextval值为:F应用题KMP算法(字符串匹配算法)较Brute(朴素的字符串匹配)算法有哪些改进?【大连海事大学1996三、1((2分)】KMP算法的主要优点是主串指针不回溯。当主串很大、不能一次读入内存且经常发生部分匹配时,KMP算法的优点就更为突出。应用题已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。【北京邮电大学1997三(10分)】模式串的next函数定义Next值为:011122312345Nextval值为:011021301105给出字符串‘abacabaaad’在KMP算法中的next和nextval数组。【北京邮电大学2000三、1(5分)】
Next:
0112123422Nextval:0102010422令t=‘abcabaa’,求其next函数值和nextva
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年度高端住宅小区物业保安劳务服务合同范本
- 2025年度购房贷款个人信息保护合同
- 2025年度游乐园项目场地使用权及设施维护合作协议
- 2025年度水田承包与农业品牌建设合作协议
- 二零二五年度白蚁防治服务合同-城市绿化带白蚁防治
- 二零二五年度游艇俱乐部船舶租赁代理合同
- 二零二五年度餐饮企业员工劳动合同法律服务与保障
- 2025年度互联网签订方协议详细流程与网络安全责任追究协议
- 二零二五年度二手电脑及配件交易合同
- 二零二五年度绿色能源股份转让合同
- 2024年人教版小学三年级信息技术(下册)期末试卷附答案
- TB 10012-2019 铁路工程地质勘察规范
- 新苏教版三年级下册科学全册知识点(背诵用)
- 乡镇风控维稳应急预案演练
- 脑梗死合并癫痫病人的护理查房
- 苏教版四年级上册脱式计算300题及答案
- 犯罪现场保护培训课件
- 扣款通知单 采购部
- 电除颤操作流程图
- 湖北教育出版社三年级下册信息技术教案
- 设计基础全套教学课件
评论
0/150
提交评论