数 据 结 构 Ch.4 串 计 算 机 学 院 肖明军 Email: xiaomj@ustc.edu.cn http://staff.ustc.edu.cn/~xiaomj.

Presentation on theme: "数 据 结 构 Ch.4 串 计 算 机 学 院 肖明军 Email: xiaomj@ustc.edu.cn http://staff.ustc.edu.cn/~xiaomj."— Presentation transcript:

1 数 据 结 构 Ch.4 串 计 算 机 学 院 肖明军

2 Ch.4 串 字符串是一种特殊的线性表，它的每个结点仅有一个字符组成 早期，串只能出现在输入输出中，以直接量形式出现，不参与运算

3 §4.1 串定义及运算 基本概念 串：零个或多个字符组成的有限序列 记为s=“a1a2……an”(n≥0) s为串名，引号中为串值
ai：字母，数字等字符 串长度：n，n=0为空串 空白串：“ ”和“”之差别

4 §4.1 串定义及运算 子串：串中任意个连续字符组成的子序列称为该串的子串，包含子串的的串称为主串 特别地：空串是任意串的子串
任意串是其自身的子串 串常量：只能引用，不能改变，一般用直接量表示 有的语言允许对其命名，如C++； const char path[]=“dir/bin/appl” 串变量：可读写，一般有名字

5 §4.1 串定义和运算 基本运算 ①求串长 ②复制 ③拼接 ④比较 ⑤子串定位 C中<string.h> 比较
相等：长度相等，且各对应位置上字符亦 相等 大小：字典序 “axy”<“ba” “baker”>“Baker”

6 §4.1 串定义及运算 子串定位 子串在主串中首次出现时，该子串首字符对应主串中的位置序号
A=“This is a string” B=“is” 序号为3 3 6 其它复杂操作：均可用基本操作构成 C中有丰富的函数

7 §4.2 串的存储结构 串是特殊线性表，节点是单个字符，故有特殊技巧 静态存储分配的顺序串 直接用定长字符向量来表示，上界预先给定
#define MaxStrSize //用户定义 Typedef char SeqString[MaxStrSize]; SeqString S; //S是可容纳255个字符的顺序串 终结符：‘\0’是串终结符，放在串值尾部 串长属性：若不设终结符 typedef struct { char ch[MaxStrSize]; //可容纳256字符 int length; }SeqString

8 §4.2 串的存储结构 动态存储分配的顺序串 用C的malloc和free动态申请和释放向量空间，有两种形式：
typedef char *string; //C中串库相当于使用此类//似定义 typedef struct { char *ch; //若串非空，则按串实际长度分配，否则为NULL int length； }Hstring

9 §4.2 串的存储结构 链串 块链存储 结点大小 大小为1： 大小为3： 存储密度d d=数据大小/结点大小

10 §4.3 串的模式匹配算法（串定位运算） 朴素的定位算法（串匹配） 主串：目标串（正文串Target，Text）
子串：模式（串）（子串，Pattern） 设T=“t0t1…tn-1” P=“p0p1…pm-1” （0≤m≤n） 通常m<<n 应用：文本编辑，基因匹配等

11 对合法的位置0≤i≤n-m（合法位移），依次将目标串中的子串T[i..i+m-1]和模式串P[0..m-1]进行比较
§4.3 串的模式匹配算法 思想： 对合法的位置0≤i≤n-m（合法位移），依次将目标串中的子串T[i..i+m-1]和模式串P[0..m-1]进行比较 若T[ i .. i+m-1]=P[0 .. m-1](即：“titi+1…ti+m-1”=“p0p1…pm-1”) 则称从位置i开始的匹配成功； 否则，存在某个0≤j≤m-1，使‘ti+j’≠‘pj’，则称从位置i开始的匹配失败

12 §4.3 串的模式匹配算法 有时需在T中找到所有有效位移 有效位移：若T[i..i+m-1]=P[0..m-1]，则i称为有效 位移
总结：朴素的串匹配算法是对合法位移检查其是否 为有效位移 有时需在T中找到所有有效位移 通常找首次出现的有效位移

13 §4.3 串的模式匹配算法 int NaiveStrMatch ( SeqString T, SeqString P ) { //顺序串上实现 int i, j, k; int m = P.length, n = T.length; for (i = 0; i<=n-m; i++) { //i为合法位移，检查其是否为有效位移 j = 0; k=i; //j指向模式，k指向目标 while(j<m && T.ch[k] == P.ch[j]){ //检查i是否为有效位置 k++; j++; //依次检查相应位置是否匹配 } if (j == m) //即T[i..i+m-1]=P[0..m-1]，i为有效位移 return i; //返回首次出现的有效位移i，匹配成功 } //end for return -1; //匹配失败，所有合法位移均不是有效位移

14 §4.3 串的模式匹配算法 该算法是将模式串看作是在目标串上向右滑动的模板

15 §4.3 串的模式匹配算法 时间： 最坏情况：对所有合法位移，均要比较到模式的最后一个字符，才能确定位移无效 即：O((n-m+1)m)≈O(n*m) // n>>m 最坏情况发生在： 目标串是 an-1b 模式串是 am-1b // 最后一次成功 用链串表示时定位运算类似

16 T：…ti-j+1…ti… ti-j+1ti-j+2 …titi+1 P： p1……pj p1……pj-1pj
§4.3 串的模式匹配算法 KMP算法（不带回溯） 下标仍从1算 原因分析 P右移1位 T：…ti-j+1…ti… ti-j+1ti-j+2 …titi+1 P： p1……pj p1……pj-1pj 原因：没有利用部分匹配的结果 若能将模式串右移一段距离，则速度更快 回溯 比较点

17 §4.3 模式匹配算法 T: a b b a b a P: a b a 失败时有：p1=t1，p2=t2，p3≠t3
§4.3 模式匹配算法 T: a b b a b a P: a b a 失败时有：p1=t1，p2=t2，p3≠t3 若将P右移1位，则p1？t2，因为 p1≠p2， p2=t p1≠t2 ，故右移1位后仍失败 ②若将P右移2位，则p1？t3，因为 p1=p3，p3≠t p1≠t3，故右移2位后仍失败 结论：上图比较失败时应直接将P右移3位（即i=1，2，3均为无效 位移），即直接比较p1和t4，比较点不回溯。 Note：上述观察告诉我们，分析模式本身，就可知道潜在的有效 位移

18 §4.3 模式匹配算法 若使比较点不回溯（i不回溯），则当 ti≠pj（T[i-j+1..i-1]=P[1..j-1]，
§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）应与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右移最大

19 …ti-j+1 …ti… ti-j+1…ti-k+1……ti p1……pj … p1……pk…pj…
§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 ？ 右移i-k+1-(i-j+1)=j-k

20 §4.3 模式匹配算法 算法 若已知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 (i<=n && j<=m) if (T[i]==P[j]) { i++; j++; //继续比较下一位 } else { //ti≠ pj k=next[j]; if (k>0) j=k ; //比较ti和pk: ti~pk else { j=1; i++; } //比较ti+1和p1:ti+1~p1 } //endif，endwhile

21 §4.3 模式匹配算法 算法 if (j>m) //匹配成功 return i-m; //注意成功时，i和j均多加了1 else return 0; //匹配失败 } 时间：循环主要取决于i只增不减，因为n>>m，所以时间为O(n)

22 整数数组：0≤next[j]<j，即0 ≤k<j 当ti≠pj时，若next[j]=k>0，则比较ti和pk，此时有:
§4.3 模式匹配算法 next数组的性质 整数数组：0≤next[j]<j，即0 ≤k<j 当ti≠pj时，若next[j]=k>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” 当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个字符相等 ？

23 当满足性质2的k有多个（即前后缀相等的子串有多个）时，应取最大的k值。 原因：k最大，模式P右移j-k最少，不丢失任何匹配机会。
§4.3 模式匹配算法 当满足性质2的k有多个（即前后缀相等的子串有多个）时，应取最大的k值。 原因：k最大，模式P右移j-k最少，不丢失任何匹配机会。 例: j 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位均失败

24 §4.3 模式匹配算法 真子串不包括自身，但包括空串 真子串：”aa” , “a” , “” 长度： k ：

25 §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时 j=1 P[1…j-1]中前后缀相等的最大真子串的长度加1(包括空串),即： Max{k|1≤k<j 且”p1…pk-1”=“pj-k+1…pj-1”} //k=1时,为空串 例： j P a b a a b c a c next[j] next[j]=

26 §4.3 模式匹配算法 next数组生成（递推法） 设next[i]=j已知，求next[i+1] (i≥1)
§4.3 模式匹配算法 next数组生成（递推法） 设next[i]=j已知，求next[i+1] (i≥1) 由性质4告知我们，对任何模式P，总有next[1]=0 成立，给出了递推基础 ∵next[1]~next[i]已知，且已知next[i]=j ∴P[1…i-1]中有： “p1…pj-1”=“pi-j+1…pi-1” //最大真子串长度为j-1 扩充一个字符pi后，比较pj~pi 若pi=pj，则P[1…j]=P[i-j+1…i] 即P[1…i]中前后缀的最大真子串长度为j，故 next[i+1]=j+1 或者 next[i+1]=next[i]+1

27 §4.3 模式匹配算法 若pi≠pj，则将求next值的问题看成是模式匹配问题，即P既为主串又为模式串
§4.3 模式匹配算法 若pi≠pj，则将求next值的问题看成是模式匹配问题，即P既为主串又为模式串 将P右移，用next[j]=k作下标，比较pk~pi 即：令j←next[j]，如此反复比较pi~pj 至pi=pj（情况①）或者 j=0，令next[i+1]=1为止 //没有一个字符与pi比较 例子自己分析 目标串： p1…pi-j+1…pi-k+1…pi-1 pi… 模式串： p1……pj-k+1…pj-1 pj… p1……pk-1 pk ？

28 §4.3 模式匹配算法 void GetNext (char p[] , int next[]) {
§4.3 模式匹配算法 void GetNext (char p[] , int next[]) { //求模式串P的next数组（递推法）i-主串指针 i=1; j=0; next[1]=0; m=P[0]; //模式串长度 while (i<m) //求next[i+1] if (j==0) next[++i]=++j; //next[i+1]=1 else //j>0 if (P[i]==P[j]) next[++i]=++j; //next[i+1]=j+1 else //pi≠pj j=next[j]; } //可改进为书上一样的算法

29 §4.3 模式匹配算法 时间：O(m) KMP算法的时间加上求next数组后为O(n+m)
§4.3 模式匹配算法 时间：O(m) KMP算法的时间加上求next数组后为O(n+m) 当n>>m时，它远远优于朴素匹配，尤其是模式串 中存在很多“部分匹配”时 但当n≈m时，朴素匹配可能更好 next数组的改进 next性质5：若ti≠pj时，设next[j]=k>0，应比较ti~pk 若已知pk=pj，则必有ti ≠pk，此时应使用next[k]=k’ (k’>0)为下标继续比较：ti~pk’

30 §4.3 模式匹配算法 即可用下述方式节省时间： 当pj=pk时，将next[j]置为next[k] 此过程可重复！ 例：
§4.3 模式匹配算法 即可用下述方式节省时间： 当pj=pk时，将next[j]置为next[k] 此过程可重复！ 例： j j P next[j] nextval[j] P a a a a b a next[j] a 改进 nextval[j] a pj p2 p3 p4 p a pk p1p2 p3 p b ti≠p2,比较ti~pnext[2] ∵p2=p1,next[2] ←next[1] ti ≠p3,ti~pnext[3], ∵p3=p2∴next[3]←next[2]

31 §4.3 模式匹配算法 求nextval算法 与书上不一样的算法，请比较
§4.3 模式匹配算法 求nextval算法 与书上不一样的算法，请比较 void GetNextVal (char P[], int nextval[]) { //求nextval i=1; j=0; nextval[1]=0; m=P[0]; while (i<m) { //已知nextval[i]，求nextval[i+1] 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)