201447 Ch,4串 数据结构 字符串是一种特殊的线性表，它的每个 Ch.4串 结点仅有一个字符组成 早期，串只能出现在输入输出中，以直 计算机学院 肖明军 接量形式出现，不参与运算 Email:xiaomj@ustc.edu.cn http://staff.ustc.edu.cn/~xiaomj 84.1串定义及运算 84.1串定义及运算 ■基本概念 子串：串中任意个连续字符组成的子序列称为 串：零个或多个字符组成的有限序列 该串的子串，包含子串的的申称为主串 记为s=“aa2…a”(n≥0) 特别地：空串是任意串的子串 s为串名，引号中为串值 任意申是其自身的子申 a:字母，数字等字符 串常量：只能引用，不能改变，一般用直接量 串长度：n,n=0为空串 表示 空白串：“”和“”之差别 有的语言允许对其命名，如C+: const char path[]=“dir/bin/appl” 串变量：可读写，一般有名字 S4.1串定义和运算 S4.1串定义及运算 ■基本运算 “子串定位 ①求串长②复制③拼接④比较⑤子串定位 子串在主串中首次出现时，该子串首字符对应主串 中的位置序号 C中 A=“This is a string”B=“is”序号为3 比较 36 相等：长度相等，且各对应位置上字符亦 。其它复杂操作：均可用基本操作构成 相等 C中有丰富的函数 大小：字典序 “axy”人“ba” “baker'”>“Baker
2014/4/7 1 数据结构 Ch.4 串 1 计 算 机 学 院 肖明军 Email: xiaomj@ustc.edu.cn http://staff.ustc.edu.cn/~xiaomj Ch.4 串 字符串是一种特殊的线性表，它的每个 结点仅有一个字符组成 早期，串只能出现在输入输出中，以直 2 早期，串只能出现在输入输出中，以直 接量形式出现，不参与运算 §4.1 串定义及运算 基本概念 串：零个或多个字符组成的有限序列 记为s=“a1a2……an”(n≥0) s为串名，引号中为串值 3 ai：字母，数字等字符 串长度：n，n=0为空串 空白串：“ ”和“”之差别 §4.1 串定义及运算 子串：串中任意个连续字符组成的子序列称为 该串的子串，包含子串的的串称为主串 特别地：空串是任意串的子串 任意串是其自身的子串 4 串常量：只能引用，不能改变，一般用直接量 表示 有的语言允许对其命名，如C++； const char path[]=“dir/bin/appl” 串变量：可读写，一般有名字 §4.1 串定义和运算 基本运算 ①求串长 ②复制 ③拼接 ④比较 ⑤子串定位 C中 比较 5 相等：长度相等，且各对应位置上字符亦 相等 大小：字典序 “axy”“Baker” §4.1 串定义及运算 子串定位 子串在主串中首次出现时，该子串首字符对应主串 中的位置序号 A=“This is a string” B=“is” 序号为3 6 3 6 其它复杂操作：均可用基本操作构成 C中有丰富的函数
2014/47 §4.2串的存储结构 串是特殊线性表，节点是单个字符，故有特殊技巧 §4.2串的存储结构 1静态存佛分配的原序审 2动态存储分配的顺序串 直接用定长字符向量来表示，上界预先给定 用C的nalloci和ree动态申请和释放向量空间，有两 #define MaxStrSize256/用户定义 种形式： Typedef char SeqString[MaxStrSizel: ①typedef char*string;C中串库相当于使用此类 SeqString S:S是可客纳255个字符的顺序率 /似定义 ◆终结符：心是串终结符，放在串值尾部 ②ypedef struct{ ◆率长具性：若不设终结符 char*ch;若串非空，则按率实际长度分配，否则为NULL typedef struct{ char chMaxStrSize:/可容纳256字符 int length; int length; Hstring SeqString §4.2串的存储结构 S4.3串的模式匹配算法（串定位运算） 3.链串 1.朴素的定位算法（串匹配） 块链存储 主串：目标串（正文串Target,Text) 子串：模式（串）（子串，Pattern) ◆结点大小 大小为1：s乙a□g囚 设T=“t6l1tn” P=“pp1p”(0m匹n)通常m<Kn 大小为3：8乙abc日e0四 应用：文本编辑，基因匹配等 女存储密度d d-数据大小结点大小 S4.3串的模式匹配算法 843串的模式匹配算法 ◆思想： 有效位移：若T正.i计m-1=P0m-1小，则称为有效 位移 对合法的位置0≤≤-m(合法位移)，依次将目标 无效位移：若Ti.i计m-1≠P0m-1,则称为无效 串中的子串T正.i+m-1和模式串P0.m-1进行比较 位移 若Tii+m-1=P0.m-lj即：“ttm"=“pwp1pal" ·总结：朴素的串匹配算法是对合法位移检查其是否 为有效位移 则称从位置开始的匹配成功： 有时需在T中找到所有有效位移 否则，存在菜个0≤m-1,使"'≠p',则称从位量i 通常找首次出现的有效位移 开始的匹配失败 2
2014/4/7 2 §4.2 串的存储结构 串是特殊线性表，节点是单个字符，故有特殊技巧 1. 静态存储分配的顺序串 直接用定长字符向量来表示，上界预先给定 #define MaxStrSize 256 //用户定义 Typedef char SeqString[MaxStrSize]; 是可容纳 个字符的顺序串 7 SeqString S; //S是可容纳255个字符的顺序串 终结符：‘\0’是串终结符，放在串值尾部 串长属性：若不设终结符 typedef struct { char ch[MaxStrSize]; //可容纳256字符 int length; }SeqString §4.2 串的存储结构 2. 动态存储分配的顺序串 用C的malloc和free动态申请和释放向量空间，有两 种形式： ① typedef char *string; //C中串库相当于使用此类 //似定义 8 ② typedef struct { char *ch; //若串非空，则按串实际长度分配，否则为NULL int length； }Hstring §4.2 串的存储结构 3.链串 块链存储 结点大小 大小为1 9 ： 大小为3： 存储密度d d=数据大小/结点大小 §4.3 串的模式匹配算法（串定位运算） 1. 朴素的定位算法（串匹配） 主串：目标串（正文串Target，Text） 子串：模式（串）（子串，Pattern） 设T=“t0t1 …tn-1” 10 0 P=“p0p1 …pm-1” （0≤m≤n） 通常m<<n 应用：文本编辑，基因匹配等 §4.3 串的模式匹配算法 思想： 对合法的位置0≤i≤n-m（合法位移），依次将目标 串中的子串T[i..i+m-1]和模式串P[0..m-1]进行比较 若T[ i i 1] P[0 1] 即 “ 11 若T[ i .. i+m-1]=P[0 .. m-1](即：“ti ti+1…ti+m-1”=“p0p1 …pm-1”) 则称从位置i开始的匹配成功； 否则，存在某个0≤j≤m-1，使‘ti+j’≠‘pj ’，则称从位置i 开始的匹配失败 §4.3 串的模式匹配算法 有效位移：若T[i..i+m-1]=P[0..m-1]，则i称为有效 位移 无效位移：若T[i..i+m-1]≠P[0..m-1]，则i称为无效 位移 总结：朴素的串匹配算法是对合法位移检查其是否 12 为有效位移 有时需在T中找到所有有效位移 通常找首次出现的有效位移
2014/47 843串的模式匹配算法 int NaiveStrMatch(SeqString T,SeqString P){顺序率上实现 §4.3串的模式匹配算法 inti,j.k; 该算法是将模式串看作是在目标串上向右滑动 int m=P.length,n=T.length; 的模板 for=:1长=n-m:i计+){瓜为合法位移，检查其是否为有效位移 j=0:k=士：心指向摸式，k指向目标 while(jm P右移1位 回湖比较点 最坏情况发生在： 目标串是an-b T:"tm"t H 模式串是am-b∥最后一次成功 P: p…p P1…PiP ·用链串表示时定位运算类似 原因：没有利用部分匹配的结果 若能将模式串右移一段距离，则速度更快 §43模式匹配算法 s43模式匹算法 T:a bb a b a b 若使比较点不回潮（不回），则当 p(T11-1, 失败时有：p=t,pt2,P 即♪的前1个字符与相应T上字符相等： ①若将P右移1位，则，？2，因为 +4pp)时，P中哪个字符应与继续比较7 P邦2，P2=2一P礼，故右移1位后仍失败 因为不动时，必定是将模式右移一段距离，所以不妨设(k) 应与继续比较。 @若将P右移2位，则p,?,因为 Kuth发现，k值仅依赖于P的前个字符的构成，与目标T无关。 P=P3,p共一P,故右移2位后仍失败 采用next1.m]数组，用next[们=k表示当tp时，下 个应与比较的是即 结论：上图比较失败时应直接将P右移3位（即i-1,2,3均为无效 位移)，即直接比较即和，比较点不回潮。 若P中任何字符均无需与1比较，则将p与比较，此时令 next=0。P右移最大 八o:上述观察告诉我们，分折横式本身，就可知道潜在的有效 位移 3
2014/4/7 3 §4.3 串的模式匹配算法 int NaiveStrMatch ( SeqString T, SeqString P ) { //顺序串上实现 int i, j, k; int m = P.length, n = T.length; for (i = 0; i>m 最坏情况发生在 15 ： 目标串是 an-1b 模式串是 am-1b // 最后一次成功 用链串表示时定位运算类似 §4.3 串的模式匹配算法 2. KMP算法（不带回溯） 下标仍从1算 原因分析 P右移1位 回溯 比较点 16 T：…ti-j+1…ti … ti-j+1ti-j+2 …ti ti+1 P： p1 ……pj p1……pj-1pj 原因：没有利用部分匹配的结果 若能将模式串右移一段距离，则速度更快 §4.3 模式匹配算法 T: a b b a b a P: a b a 失败时有：p1=t1，p2=t2，p3≠t3 ①若将P右移1位，则p1？t2，因为 p ≠p p =t p ≠t 故右移1位后仍失败 17 p1≠p2， p2=t2 p1≠t2 ，故右移1位后仍失败 ②若将P右移2位，则p1？t3，因为 p1=p3，p3≠t3 p1≠t3，故右移2位后仍失败 结论：上图比较失败时应直接将P右移3位（即i=1，2，3均为无效 位移），即直接比较p1和t4，比较点不回溯。 Note：上述观察告诉我们，分析模式本身，就可知道潜在的有效 位移 §4.3 模式匹配算法 若使比较点不回溯（i不回溯），则当 ti ≠pj （T[i-j+1..i-1]=P[1..j-1]， 即P的前j-1个字符与相应T上字符相等： ti-j+1…ti-1=p1…pj-1）时，P中哪个字符应与ti 继续比较？ 因为i不动时，必定是将模式右移一段距离，所以不妨设pk（k<j） 应与 继续比较 18 ti 。 Knuth发现，k值仅依赖于P的前j个字符的构成，与目标T无关。 采 用 next[1..m] 数组，用 next[j]=k 表示当 ti ≠pj 时，下一 个应与ti 比较的是pk 若P中任何字符均无需与ti比较，则将p1与ti+1比较，此时令 next[j]=0。P右移最大
201447 S4.3模式匹配算法 §43模式匹配算法 ■算法若已知next1.m则匹配算法如下 P的右移位数为：j-next[j们 int KMPMatch(char Tll,char Pll){/TIo和P叫O分别表示长度 少右移 n-TI01;m-P0;/长度 jPl:开始rp j1… j+1…tk+1…t while(0) jPk;比较t和ptrp else{ j-l;it+; }/比较和即t+P 】//endif.endwhile S43摸式匹配算法 S43模式匹配算法 算法 next数组的性质 if>m)匹配成功 ①整数数组：0飞next[jl0,则比较t和p,此时有 Tk+1-1-P叫1k-11/长度为k-1 else Tij+1i-1P叫1j-11失败前部分匹配，长度为j-1 return0:/匹配失败 Pjk+lj-i-PILk-Ip…pL"-p-k+p” 3 当邦，时，k的值应等于串P1小中前后缀相等的子串的长度 加1 ◆时间：循环主要取决于只增不减，因为>m,所 以时间为O(n P1…p-k+1…P-iPj- ∥前j-1个字符相等 P右移jk位： P1…pk-iPk ]/前k-1个字符相等 22 843模式匹配算法 §4.3模式匹配算法 ③当满足性质2的k有多个（即前后绿相等的子串有多 真子串不包括自身，但包括空串 个)时，应取最大的k值。 原因：k最大，模式P右移-k最少，不丢失任何匹配 真子串：”aa”,“a”,“” 机会。 长度：210 例：j1234 Taaa是bbbb P右移1位，匹配成功 k:321 Pa aa b P右移2位、3位均失败 在P13引中，k=3最大，j-k=1位右移最少，k=2, k=1时失去匹配机会 即P13引中，前后绿相等的最大真子串为 P12=P231,长度+1-3-k
2014/4/7 4 §4.3 模式匹配算法 P的右移位数为：j-next[j] …ti-j+1 …ti … ti-j+1…ti-k+1……ti p1……pj… p1……pk…pj … j-k 右移j-k ？ 19 p1……pj… p1……pk…pj … 右移i-k+1-(i-j+1)=j-k 算法 若已知next[1…m],则匹配算法如下： int KMPMatch ( char T[] ,char P[] ) { //T[0]和P[0]分别表示长度 n=T[0] ; m=P[0] ; //长度 i=j=1; //开始 t1~p1 while (i0) j=k ; //比较ti 和pk: ti ~pk else { j=1; i++; } //比较ti+1和p1:ti+1~p1 } //endif，endwhile 算法 if (j>m) //匹配成功 return i-m; //注意成功时，i和j均多加了1 else return 0; //匹配失败 §4.3 模式匹配算法 21 } 时间：循环主要取决于i只增不减，因为n>>m，所 以时间为O(n) next数组的性质 ① 整数数组：0≤next[j]0，则比较ti 和pk，此时有: T[ i-k+1..i-1 ]=P[ 1..k-1 ] //长度为k-1 T[ i-j+1..i-1 ] =P[ 1..j-1 ] //失败前部分匹配，长度为j-1 P[ j-k+1..j-1 ]=P[1..k-1] // “p1…pk-1”=“pj-k+1…pj-1” §4.3 模式匹配算法 22 当ti ≠pj 时，k的值应等于串P[1…j-1]中前后缀相等的子串的长度 加1 T：…ti-j+1… ti-k+1 … ti-1 ti … p1……pj-k+1…pj-1pj … // 前j-1个字符相等 P右移j-k位： p1……pk-1pk… // 前k-1个字符相等 ？ ③ 当满足性质2的k有多个（即前后缀相等的子串有多 个）时，应取最大的k值。 原因：k最大，模式P右移j-k最少，不丢失任何匹配 机会。 例: j 1 2 3 4 Ta a a a b b bb §4.3 模式匹配算法 P右移1位，匹配成功 23 T a a a a b b b b P a a a b 在P[1..3]中，k=3最大，j-k=1位右移最少，k=2， k=1时失去匹配机会 即P[1..3]中，前后缀相等的最大真子串为 P[1..2]=P[2..3]，长度+1=3=k P右移1位，匹配成功 P右移2位、3位均失败 §4.3 模式匹配算法 真子串不包括自身，但包括空串 真子串：”aa” , “a” , “” 长度： 2 1 0 k ： 3 2 1 24
2014/47 §4.3模式匹配算法 $4.3模式匹配算法 ④若P1.于-川不存在首尾相同的字符串，或者说仅存在长度为零的 ■next数组生成（递推法） 相同前后绿（空串）子串，则k一1，即p,与继续比较 特别地，若（即抑），则P中任何字符无法与缝蝶比较，P 设next=j已知，求nexti+1小e1) 右移1位，将p和t继续比较。按next定义，可取next1-0(对 由性质4告知我们，对任何模式P,总有mext1=0 任何P成立)。 成立，给出了递推基础 综上所述，当邦时 ,next[1]-next[已知，且已知next i=j 0 .P1i1中有： nxt-P1.…小l中前后佩相等的量大离子事的长度加1（包括空率），即： “p…p.”=“p1P”最大真子串长度为j-门 am因sy且”p4p"-一pk…p=I时为空审 扩充一个字符p后，比较pp 例， ①若pp,则P1.jP时1. j|12345678 即P1.中前后缀的最大真子串长度为j,故 Pa b aa b c a c next i+-1-j+1或者next i+1=next i+1 nextlil 0 11 22 3 1 2 84.3模式匹配算法 §43模式匹配算法 void GetNext (char pll,int next){ ②考印却，则将求aext值的问题看成是模式匹配问题， 即P既为主串又为模式串 1求模式串P的next数组（递推法）i1-主串指针 将P右移，用next=k作下标，比较pp: i-1;j-0;next 1]-0; 即：令j-next[jl,如此反复比较prp m-P叫0：模式串长度 至pp(情况①)或者 while(ism)求nexti+1 j=0,令next+1-1为止/没有一个字符与p,比较 if (j=-0)next++il-++j;//next i+1]-1 例子自己分析 else /j>0 目标串： p1…Pt1…P-k1…P-1p if (Plil-Pljl) 模式串： next++i]-++j;//nexti+1]-j+l PP-k+1…P-1P else l/pP j-nextijl; 1可改进为书上一样的算法 §43模式匹配算法 §4.3模式匹配算法 时间：0(m) 即可用下述方式节省时间： 当p=p,时，将next置为nextk KMP算法的时间加上求nex数组后为O(+m) 此过程可重复！ 当>m时，它远远优于朴素匹配，尤其是模式串 中存在很多“部分匹配”时 例： 但当≈m时，朴素匹配可能更好 j1 2 3 4 5 jP next[j]nextvallj ■next数组的改进 Paaaab Ia 0 0 next性质5：若tp时，设next=k>0,应比较t~p 1 2 3 4 2a 1 0 尖叫 2 若已知p=p,则必有lpk,此时应使用next[k=k 0 P 4a3 0 (k>0)为下标继续比较：tP Px- 5
2014/4/7 5 §4.3 模式匹配算法 ④若P[1…j-1]不存在首尾相同的字符串，或者说仅存在长度为零的 相同前后缀（空串）子串，则k=1，即p1与ti 继续比较 特别地，若j=1（即ti ≠p1），则P中任何字符无法与ti 继续比较，P 右移1位，将p1和ti+1继续比较。按next定义，可取next[1]=0（对 任何P成立）。 综上所述，当ti ≠pj 时 25 0 j=1 P[1…j-1]中前后缀相等的最大真子串的长度加1(包括空串),即： Max{k|1≤k0 if (P[i]==P[j]) next[++i]=++j; //next[i+1]=j+1 else //pi ≠pj j=next[j]; } //可改进为书上一样的算法 §4.3 模式匹配算法 时间：O(m) KMP算法的时间加上求next数组后为O(n+m) 当n>>m时，它远远优于朴素匹配，尤其是模式串 中存在很多“部分匹配”时 29 但当n≈m时，朴素匹配可能更好 next数组的改进 next性质5：若ti ≠pj 时，设next[j]=k>0，应比较ti ~pk 若已知pk=pj ，则必有ti ≠pk，此时应使用next[k]=k’ (k’>0)为下标继续比较：ti ~pk’ §4.3 模式匹配算法 即可用下述方式节省时间： 当pj =pk时，将next[j]置为next[k] 此过程可重复！ 例： j 1 2 3 4 5 j P next[j] nextval[j] 30 j 1 2 3 4 5 j P next[j] nextval[j] P a a a a b 1 a 0 0 next[j] 0 1 2 3 4 2 a 1 0 改进 nextval[j] 0 0 0 0 4 3 a 2 0 pj p2 p3 p4 p5 4 a 3 0 pk p1p2 p3 p4 5 b 4 4 ti ≠p2,比较ti ~pnext[2] ∵p2=p1,next[2] ←next[1] ti ≠p3,ti ~pnext[3], ∵p3=p2∴next[3]←next[2]
201447 843模式匹配算法 ■求nextval算法 与书上不一样的算法，请比较 void GetNextVal (char Pll,int nextval[l)(//nextval i-1;j-0; nextval[1|-0;m-P[0]; while (i0&&P间aPjD -nextval[jl:∥出循环时-0或PPjl i计+：j++: ifPI间-PD nextvallil=nextvall:∥性质5 else nextvalli]-j;//nextvalli+l]j+l 3 时间仍为Om 6
2014/4/7 6 §4.3 模式匹配算法 求nextval算法 与书上不一样的算法，请比较 void GetNextVal (char P[], int nextval[]) { //求nextval i=1; j=0; nextval[1]=0; m=P[0]; while (i0 && P[i] != P[j]) 31 while (j 0 && P[i] ! P[j]) j=nextval[j]; // 出循环时j=0或P[i]=P[j] i++; j++; if (P[i] ==P[j]) nextval[i] = nextval[j]; // 性质5 else nextval[i] = j; // nextval[i+1] = j+1 } } 时间仍为O(m)