2015考研计算机数据结构进阶精讲课程配套讲义

C．模式匹配是串的一种重要运算D．串既可以采用顺序，也 S1‘ABCDEFS2‘9898’,S3‘###,S4‘012345,(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))其结果为（E A．ABC###G0123B．ABCD###2345C．ABC###G2345 E．ABC###G1234F．ABCD###1234设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（。 ababaaababaanext数组为（C 字符串‘ababaabab’的nextval为（A。 D．(0,1,0,1,0,1,0,1,1（FA．0111221112345671B．0111212112345611C．01110D．0111223112345671E．0110011101100170F．0110 n（n>0所以本题的答案为：8*（8+1）/2+1=37。故选B。空且不同于S本身）的个数为（D。 E.(n2/2)-(n/2)-1 串的长度是指（B 空格串是指(1)由空格字符（ASCII32）所组成的字符串，其长度等于(2)空格个数。 字符 称为该串的子串INDEX‘DATASTRUCTURE’，‘STR）=_5_)模式串P=‘abaabcac’的next函数值序列 TPTP的子串的过程称为(1)模式匹配，又P为(2)模式串。串是一种特殊的线性表，其特殊性表现在(1)其数据元素都是字符；串的两种最基本的方式是(2)顺序、(3)和链式；两个串相等的充分必要条件是(4)串的长度相等且两串中对应位置的字符也相等。ASSIGN（S，UASSIGN（V，SUBSTR（S，INDEX（s，t，LEN（t）+1；ASSIGN（m，‘ww）求 strcpyvoidstrcpy(char*s,char*t)/*copytto *s++=*t++或（*s++=*t++）!=‘\0’}aaint (1)chars[ (2) for(j--;i<j &&s[i]==s[j];i++,j--); (3)i>=j }PROCget_next(t:string,VARnext:ARRAY[1..t.len]OFinteger);j:=1; IFk=0ORt.ch[j]=t.ch[k]THENBEGINj:=j+1;ELSEk:=(2)next[k] IFs[i]=t[j]THEN [(1)i：=i+1 ELSE[(3)i:=i-j+2 IFj>mt (5)i-mt（或i:=i-j+1）; 1011t串 next[j]0 答：next数组值为 模式为答：（1）pnextval0110132（pnext0111232。（2）利用KMP(改进的nextval)算法，每趟匹配过程如下：第一趟匹配：abcaabbabcabaacbacba 第二趟匹配：abcaabbabcabaacbacba 第三趟匹配：abcaabbabcabaacbacba abcaabbabcabaacbacba(成功解答：以顺序结构表示串，设计算法。求串S中出现的第一个最长重复子串及其位置[题目分析]s表示串，重复子串的含义是由一个或多个连续相等的字符组max0max相比，若比max大，则需要更新max，并用index记住其开始位置。{intindex=0,max=0; //index记最长的串在s串中的开始位置，max记其长度intlength=1,i=0,start=0; //length记局部重复子串长度，i为字符数组下标//{if(max<lengthmax=length;index=start;当前重复子串长度大，则更新maxi++;start=i;length=1;//初始化下一重复子串的起始位置和长度}最后一个字符下标是n-1，当i最大为n-2时，条件语句中s[i+1]正好是s[n-1]，即最后一个1，表示一个字符自然等于其身。算法的时间复杂度为