第四章 串String.pptVIP

a b a c a a c a b c a b a c a b a a a b a c a b 1 2 3 4 5 6 a b a c a b 7 a b a c a b 8 9 10 11 12 a b a c a b 13 a b a c a b 14 15 16 17 18 19 2 1 2 1 1 0 Next b a c a b a P 6 5 4 3 2 1 j a a a a b a a a a a a a a a a b a a a a a b 1 2 3 4 5 6 a a a a a b 5 4 3 2 1 0 Next b a a a a a P 6 5 4 3 2 1 j a a a a a b 7 a a a a a b 8 a a a a a b 9 ......Si-j Si-j+1 Si-j+2 Si-k+2 ... Si-k Si-k+1 ... ... Si p1 p2 pj-k pj-k+1 ... pj-2 pj-1 p1 p2 pk ... pk-2 pk-1 Si-2 Si-1 pj-k+2 pj ≠ || || || || || || || || || || || || 不需要比较 p1 p2 ... pnext[k] ........ 修正next 5 0 0 0 0 0 nextval b a a a a a T 6 5 4 3 2 1 j void get_nextval(SString T,int nextval[]) { //求模式串T的next函数修正值并存如数组nextval j=1; nextval[j]=0; k=0; while(jT[0]) if(k==0||T[j]==T[k]) {++j; ++k; if(T[j]!=T[k]) nextval[j]=k; else nextval[j]=nextval[k]; } else k=nextval[k]; }//get_nextval i1+j-1=i2 i1=i2-j+1 i1+1=i2-j+2 * * k=0表示之前不可能匹配，S的指针也要往后移 k=1表示与第一个字符比 * next[j]=k 表示p[1~k-1]=p[j-k+1~j-1] pj=pk, p[1..k]=p[j-k+1..j] next[j+1]=k+1 * T(m)=O(m) 第四章 串String 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 一、串的概念(string) 字符串是 n ( ? 0 ) 个字符的有限序列， 记作 S : ‘c1c2c3…cn’ 其中，S 是串名字 c1c2c3…cn是串值 ci 是串中字符 n 是串的长度 i 是字符ci在串S中位置 4.1 串类型的定义 设有两个字符串S1和S2： S1 =‘adbcgsdbcdf’ S2 =‘dbc’ S1称为主串， S2称为子串 两个字符串相等当且仅当 （1）串长相等 （2）对应位置的字符相等 空串是任意串的子串 任意串 S 都是 S 本身的子串 真子串：非空且不为自身的子串 子串S2在主串S1中的位置 子串在主串中首次出现时子串第一个字符在主串的位置 设有两个字符串S1和S2： S1 =‘adbcgsdbcdf’ S2 =‘dbc’ 线性表的大多以元素为操作对象 串通常以整个串作为操作对象 线性表的存储方法同样适用于字符串 二、串的抽象数据类型的定义 ADT String { 数据对象：D={ai| ai∈CharacterSet； i=1,2,…,n,；n≥0} 数据关系：R1={ai-1, ai| ai-1, ai∈D； i= 2,…,n} 基本操作： StrAssign (T , chars) 初始条件：chars是字符串常量。 操作结果：生成一个其值等于chars的串T。 StrCopy (T , S) 初始条件：串S存在。 操作结果：由串S复制得串T。 StrEmpty (S) 初始条件：串S存在。 操作结果：若S为空串，则返回TRUE，否则返回FALSE。 StrLength (S) 初始条件：串