5字符串

5字符串数据与算法 2012-2013年秋季学期 1 清华大学电子工程系陈健生 jschenthu@tsinghua.edu.cn 字符串 2 “This is a string” “2012.4.30 15:00” “6*((9+11)/2-3*4)” “@%^&*!…” … 《数据结构与算法》 6.8 • 什么是字符串 • 字符串的ADT • 高级语言中的字符串 • 字符串的模式匹配 3  ...

数据与算法 2012-2013年秋季学期 1 清华大学电子工程系陈健生 jschenthu@tsinghua.edu.cn 字符串 2 “This is a string” “2012.4.30 15:00” “6*((9+11)/2-3*4)” “@%^&*!…” … 《数据结构与算法》 6.8 • 什么是字符串 • 字符串的ADT • 高级语言中的字符串 • 字符串的模式匹配 3  字符串(串)：S = “I’m not a string”；  字符串是零个或有限多个字符组成的序列；  串名：S，串值：I’m not a string，串长：16；  字符串是常用的非数值处理的数据类型；  可理解为数据元素为字符的线性表；  特别的： ◦ 空串长度为0，记为 S=Ф 或 S=“” ◦ “a”≠‘a’ , “ ˽”≠“” 4 什么是字符串  字符在串中的序号称为字符在串中的位置；  字符串的二元关系 ◦ 两个字符串：S1 = “a0 a1…am-1” S2 = “b0 b1…bn-1”； ◦ S1 = S2当且仅当：m=n 且 ai= bi (i=0,1,…,m-1)； ◦ S1 < S2 若下列两个条件之一满足(字典序)：  mT，则返回值>0；若S=T，则返回值 =0；若S 标准库 include ◦ char* strcpy(char*, char*) ◦ strcmp, strlen, strcat, strstr, …  C++标准库 include (not string.h!) ◦ string类(typedef basic_string string) ◦ copy, compare, length, +=, substr, find, … 高级语言中的字符串 16  微软ATL/MFC include ◦ CString类 (typedef ATL::CStringT string) ◦ CloneData, Compare, GetLength, Concatenate, Mid, Find, …  Java java.lang ◦ String类，非可变类 ◦ copyValueOf, equals, length, concat, substring, IndexOf, … 高级语言中的字符串 • 什么是字符串 • 字符串的ADT • 高级语言中的字符串 • 字符串的模式匹配 17 18 int index(String S, String T, int pos){ n = strlength(S); //主串长度 m = StrLength(T); //模式串长度 i = pos; //搜索起始点 while(i<=n-m){ SubString(sub, S, i, m); //从i取长度m子串 if(StrCompare(sub, T)) //与待查模式串比较 i++; //相等返回当前位置 else return i; } } if(i==n-m+1) return -1; //无匹配子串  index(ADT), strstr(C), find(C++), Find(MFC), IndexOf(Java) 字符串的模式匹配 19  字符串精确模式匹配：给定长主串S(长度n) 和模式串T(长度m)，用理想的时间空间代价从S中找出和T相等的子串并返回其位置，找不到则匹配失败.  串模式匹配的应用(精确或模糊) ◦ 文本编辑； ◦ 程序开发； ◦ 搜索引擎； ◦ 生物信息学（DNA匹配）； ◦ 杀毒软件； ◦ 文献查重 … 字符串的模式匹配 20  字符串精确模式匹配算法 ◦ 蛮力法(Brute-Force)； ◦ KMP算法； ◦ BM算法； ◦ Horspool算法； ◦ Z-Box算法； ◦ Sunday算法； ◦ Fastsearch算法； ◦ KR算法； ◦ … 字符串的模式匹配 21  Brute-Force匹配算法 ◦ 算法思想：将模式串T和主串S每个位置开始的子串都进行比较. Linux C 源代码： char * strstr(register const char *S, register const char *T) { register const size_t len = strlen(T); if (len == 0) return (char *)S; while (*S != *T || strncmp(S, T, len)) if (*S++ == '\0') return (char *)NULL; return (char *)S; } 字符串的模式匹配 22  蛮力(Brute-Force)匹配算法 ◦ 最坏情况下算法的时间复杂度为𝑜 𝑚 × 𝑛 ； ◦ 最坏情况发生在匹配失败或是S的子串和T差别小:  S = “ooo…ooh”  T = “ooh” ◦ 常出现在图像数据或DNA数据中，自然语言较少见； ◦ 可用后缀(自右向左)蛮力法加以改善；  蛮力法的特点 ◦ 算法思想直接，易于正确实现； ◦ 效率往往低下，仅适用于小规模问题； ◦ 往往可以作为参照测试复杂算法. 字符串的模式匹配 23  如何改善匹配效率? ◦ Linux trick: 减少函数调用次数； ◦ 前后缀比较降低最坏情况出现可能； ◦ …… ◦ 本质问题：如何有效地减少比较次数？如何有效地减少比较次数如何有效地提高如何有效地提高如何有效地提高如何有效地提高如何有效地提高多余的步骤! ‘地’字没有出现在模式串前缀中字符串的模式匹配 24  Donald E. Knuth (高纳德) ◦ 美国计算机科学家 (1938~)； ◦ 斯坦福大学计算机系教授(1992荣休 Emeritus）； ◦ ‘数据结构’体系的初创者之一； ◦ 排版软件TeX和METAFONT的作者； ◦ 计算机程序设计巨著《The Art of Computer Programming》作者； ◦ 并因此书获得1974年图灵奖； ◦ 奖励找出他的著作中错误的人2.56美元； ◦ 1977年与学生合作发表 Knuth-Morris-Pratt 算法；字符串的模式匹配 25  Knuth-Morris-Pratt算法 ◦ 模式串从左向右移动，匹配也从左向右； ◦ 匹配过程中出现不匹配字符时，尽量向右侧移动最大可能的距离，避免多余的比较； a b c d a b c e c f a b c d a b c a a b c d a b c a 略去三步移动… j i j 字符串的模式匹配 26 a b c d a b c e c f a b c d a b c a a b c d a b c a a b c d a b c a a b c d a b c a a b c d a b c a 字符串的模式匹配 27 a b c d a b c e c f a b c d a b c a 𝑆0 𝑆1 𝑆2 𝑆3 𝑆4 𝑆5 𝑆6 𝑆7 𝑆8 𝑆9 𝑆11 𝑆12 𝑇0 𝑇1 𝑇2 𝑇3 𝑇4 𝑇5 𝑇6 𝑇7  匹配过程隐含信息的利用 ◦ 𝑆0𝑆1…𝑆6 = 𝑇0𝑇1…𝑇6 𝑆4𝑆5𝑆6=𝑇4𝑇5𝑇6； ◦ 𝑆7 ≠ 𝑇7； ◦ 而模式串中 𝑇0𝑇1𝑇2 = 𝑇4𝑇5𝑇6； ◦ 至多移动四步之后必有 𝑆4𝑆5𝑆6 = 𝑇0𝑇1𝑇2； ◦ 仅需继续比较𝑆7和𝑇3即可! a b c d a b c a 𝑇0 𝑇1 𝑇2 𝑇3 𝑇4 𝑇5 𝑇6 𝑇7 字符串的模式匹配 28 a b c d a b c e c f a b c d a b c a 𝑆0 𝑆1 𝑆2 𝑆3 𝑆4 𝑆5 𝑆6 𝑆7 𝑆8 𝑆9 𝑆11 𝑆12 𝑇0 𝑇1 𝑇2 𝑇3 𝑇4 𝑇5 𝑇6 𝑇7  如何保证没有移动过多步？ ◦ 𝑇1𝑇2…𝑇6 ≠ 𝑇0𝑇1…𝑇5 (移动一步肯定不匹配) ◦ 𝑇2𝑇3…𝑇6 ≠ 𝑇0𝑇1…𝑇4 (移动两步肯定不匹配) ◦ 𝑇3𝑇4…𝑇6 ≠ 𝑇0𝑇1…𝑇3 (移动三步肯定不匹配) ◦ 𝑇0𝑇1𝑇2 = 𝑇4𝑇5𝑇6 (移动四步可能匹配!) a b c d a b c a 𝑇0 𝑇1 𝑇2 𝑇3 𝑇4 𝑇5 𝑇6 𝑇7 a b c d a b c a 𝑇0 𝑇1 𝑇2 𝑇3 𝑇4 𝑇5 𝑇6 𝑇7 字符串的模式匹配 29  KMP算法步骤一 ◦ 分析模式串T，找出其内部自匹配特性； ◦ 假设j位置不匹配，找出𝑇0𝑇1…𝑇𝑗−1中最长的等值前缀子串和后缀子串； ◦ 𝑇0𝑇1…𝑇𝑗−1 = 𝑎𝑏𝑐𝑑𝑎𝑏𝑐；  前缀：∅, 𝑎, 𝑎𝑏, 𝑎𝑏𝑐, 𝑎𝑏𝑐𝑑, 𝑎𝑏𝑐𝑑𝑎, 𝑎𝑏𝑐𝑑𝑎𝑏；  后缀：∅，𝑐, 𝑏𝑐, 𝑎𝑏𝑐, 𝑑𝑎𝑏𝑐, 𝑐𝑑𝑎𝑏𝑐, 𝑏𝑐𝑑𝑎𝑏𝑐. a b c d a b c a 0 j a b c d a b c a 字符串的模式匹配 30  部分匹配串 ◦ 𝑇0𝑇1…𝑇𝑗中最长的等值前缀子串和后缀子串称为位置j处的部分匹配串； ◦ 仅需记录部分匹配串的长度； ◦ Next(j) =位置j处的部分匹配串长度； ◦ 匹配过程中字符不匹配发生时：𝑆𝑖 ≠ 𝑇𝑗  模式串：𝑗 𝑁𝑒𝑥𝑡 𝑗 − 1 (𝑗 > 0) ；  主串： 𝑖不变 𝑗 > 0 或 +1 (𝑗 = 0) . j 0 1 2 3 4 5 6 7 Tj a b c d a b c a Next(j) 0 0 0 0 1 2 3 1 字符串的模式匹配 31  Next()函数的实现 void Next(char *T, int* N) { int m = strlen(T); N[0] = 0; int i=1, j=0; while(i0) j=N[j-1];//用部分匹配串对齐 else N[i++]=0; //串头时部分匹配串长0 } } } 字符串的模式匹配 32 { int m = strlen(T); N[0] = 0; int i=1, j=0; while(i0) j=N[j-1]; else N[i++]=0; } } } 字符串的模式匹配 T a b c d a b c a m=8 N[] 0 i=1,j=0 N[] 0 0 i=1,j=0 T[1]≠T[0] N[] 0 0 0 i=2,j=0 T[2]≠T[0] N[] 0 0 0 0 i=3,j=0 T[3]≠T[0] N[] 0 0 0 0 1 i=4,j=0 T[4]=T[0] N[] 0 0 0 0 1 2 i=5,j=1 T[5]=T[1] N[] 0 0 0 0 1 2 3 i=6,j=2 T[6]=T[2] N[] 0 0 0 0 1 2 3 i=7,j=3 T[7]≠T[3] N[] 0 0 0 0 1 2 3 i=7,j=0 T[7]=T[0] N[] 0 0 0 0 1 2 3 1 i=8,j=1 33  KMP算法步骤二 ◦ 自左向右逐字符匹配; ◦ 失配时根据Next值移动模式串T:j=Next(j-1); ◦ 移动的步数本质上由模式串T决定! a b c d a b c e c f a b c d a b c a Next 0 0 0 0 1 2 3 1 Next(6) a b c d a b c a i j=7 J=3 字符串的模式匹配 34 int KMP(char* S, char* T){ int n=strlen(S), m=strlen(T); int i=0, j=0; Next(T, N); while(i0) j=N(j-1); //失配移动模式串 else i++; } } return -1; //匹配失败 } 字符串的模式匹配 35 a b a c a a b a c c a b a c a b a a b b a b a c a b 1 2 3 4 5 6 j = Next(4)=1 a b a c a b 7 j = Next(0)=0 a b a c a b 8 9 10 11 12 j = Next(3)=0 a b a c a b 13 i++ a b a c a b 14 15 16 17 18 19 匹配成功 Next 0 0 1 0 1 2 a b a c a b 字符串的模式匹配 36  KMP算法的复杂度 void Next(char *T, int* N) { … … while(i0) j=N[j-1]; //j至少减1? else N[i++]=0; //i增加1 } } } 字符串的模式匹配 37  KMP算法的复杂度 ◦ Next函数中While循环的每一层：i增加1 或者移动量i-j至少加1； ◦ 因此Next循环不超过2m次，复杂度为O(m)； ◦ 同样的，KMP函数中的While循环也不超过2n次； ◦ KMP算法最差情况复杂度为O(m+n),远好于蛮力法； ◦ 其代价仅是增加了与模式串等长的数组 Next. 字符串的模式匹配思考题 38 试编写程序实现带有通配符的串匹配： • 模式串中可能包含通配符 ‘*’; • 主串中不含有字符 ‘*’; • 通配符 ‘*’ 表示任意字符或子串; • 例如 • 主串=‘this is a difficult problem’; • 模式串=‘diff*prob’，则可以匹配; • 模式串=‘diff*is’，则不可以匹配. 39 /* Q & A */

                    本文档为【5字符串】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

5字符串

你可能还喜欢