数据结构与算法(Python语言描述)课件DS_041_串

2020/5/28,第四章串,1,串与模式匹配,2016Fall数据结构,文本,字符串的应用？,2020/5/28,第四章串,2,求串长取子串定位子串（串匹配）子串替换两个串的连接,串的常用操作,2020/5/28,第四章串,3,C语言函数库中提供的串处理函数gets(str)：输入一个串；puts(str)：输出一个串；strcat(str1,str2)：串联接函数；strcpy(str1,str2,k)：串复制函数；strcmp(str1,str2)：串比较函数；strlen(str)：求串长函数；C+标准库中的string类,=,!=,=,+,=,size,assign,append,compare,find,replace,reserve,C/C+字符串的操作,2020/5/28,第四章串,4,顺序存储静态数组动态数组块链存储链式，每个结点存储一定长度的子串,串的存储表示,2020/5/28,5,第四章串,#defineMAXSTRLEN255typedefunsignedcharSStringMAXSTRLEN+1;/用户可在255以内定义最大串长,/超过予定义长度的串值则被舍去，称之为“截断”;/0号单元存放串的长度,顺序存储表示静态数组,2020/5/28,6,第四章串,typedefstructchar*ch;/按串长分配存储区intlength;/串长度HString;,顺序存储表示动态数组,2020/5/28,7,第四章串,#defineCHUNKSIZE80/块大小typedefstructChunkcharchCUNKSIZE;structChunk*next;Chunk;typedefstruct/串的链表结构Chunk*head,*tail;/串的头和尾指针intcurlen;/串的当前长度LString;,块链存储表示,2020/5/28,8,第四章串,str是不变类型对象创建后，内容（和长度）不变采用顺序存储表示动态数组,Python字符串类型str,串匹配与KMP算法,2020/5/28,10,第四章串,许多计算机应用的最基本操作是字符串匹配。如用编辑器或字处理系统工作时，在文本中查找单词或句子（中文字或词语），在程序里找拼写错误的标识符等email程序的垃圾邮件过滤器，google等网络检索系统各种防病毒软件，主要靠在文件里检索病毒模式串在分子生物学领域：DNA细胞核里的一类长分子，在遗传中起着核心作用。DNA内有四种碱基：腺嘌吟(adenine)，胞嘧啶(cytosine)，鸟嘌吟(guanine)，胸腺嘧啶(thymine)。它们的不同组合形成氨基酸、蛋白质和其他更高级的生命结构DNA片段可看作是a,c,g,t构成的模式，如acgatactagacagt考查在蛋白质中是否出现某个DNA片段，可看成与该DNA片段的串匹配问题。DNA分子可以切断和拼接，切断动作由各种酶完成，酶也是采用特定的模式确定剪切位置,串匹配,实际中模式匹配的规模（n和m）可能非常大，而且有时间要求被检索的文本可能很大网络搜索需要处理亿万的网页防病毒软件要在合理时间内检查数以十万计的文件（以GB计）运行在服务器上的邮件过滤程序，可能需要在一秒钟的时间内扫描数以万计的邮件和附件为疾病/药物研究/新作物培养等生物学工程应用，需要用大量DNA模式与大量DNA样本（都是DNA序列）匹配由于在计算机科学、生物信息学等许多领域的重要应用，串模式匹配问题已成为一个极端重要的计算问题。高效的串匹配算法非常重要有几个集中关注字符串匹配问题的国际学术会议，曾经有过专门的国际竞赛（见wiki页和万维网）目前全世界一大半的计算能力是在做串模式匹配（做DNA分析）,串匹配,matching(t,p)#index(t,p)返回子串p在t中的位置；若不存在，返回-1t=t0t1t2tn-1称为主串（目标串）p=p0p1p2pm-1称为子串（模式串）通常有mn,串匹配（模式匹配）子串定位,2020/5/28,第四章串,13,defnave_matching(t,p):j,i=0,0whilejlen(t)andilen(p):iftj=pi:j,i=j+1,i+1else:#不同时，j回溯，i回到头j,i=j-i+1,0ifi=len(p):returnj-ireturn-1,朴素的串匹配算法,2020/5/28,第四章串,14,2020/5/28,第四章串,15,朴素的串匹配算法,每次匹配失败时，j回溯到i-j+1，i回溯到0效果：模式每次向前滑动一步，从头比较；时间复杂度：O（n*m）例：t50=0000001，p5=00001比较次数：(50-5)*5+5=(n-m+1)*m=O(n*m),算法的缺陷,2020/5/28,16,第四章串,是一个高效串匹配算法时间复杂度：O(n+m)由D.E.Knuth和V.R.Pratt提出，J.H.Morris几乎同时发现，因此称KMP算法。,KMP算法,2020/5/28,第四章串,17,2020/5/28,第四章串,18,KMP算法示意图,思想：当tj!=pi时，j指针不回溯，i回溯到nexti，让tj与pnexti继续比较；效果：模式向前滑动i-nexti步，从nexti处开始比较，nexti越小，滑动越远！,KMP算法,2020/5/28,19,第四章串,defmatching_KMP(t,p,next):j,i=0,0whilejlen(t)andi1时，nexti=“串长”串：p0.i-1的最长的、前缀、后缀、真子串最长：不能推得太远；前缀：由前推过来；后缀：对齐；真子串：至少向前滑一步；可以是空串，此时串长为零。i=1时，next1=0【上面Case的特殊情形】p0.1-1=p0没有真字串，则前后缀串也是空串直接：p1与tj比较失败，则应让p0与tj继续比较i=0时，next0=-1p0与tj比较失败，此时i、j指针应同时后移，让p0与tj+1去比若认为j不动，则p-1在和tj“对齐”,next的定义,2020/5/28,23,第四章串,T=aaaabnext：-10123T=abaaabcacnext：-100111201,例：利用“最长前后缀串”方法求next,2020/5/28,24,第四章串,“递推”利用已知的计算结果：next0，nexti，来求nexti+1,next的递推计算,2020/5/28,25,第四章串,2020/5/28,第四章串,26,已知next0=-1,nexti=k,求nexti+1=?,a,B,a,x,a,B,a,设nexti=k若：pi=pk，则：nexti+1=k+1若：pi!=pk，则需往后回朔，检查pi=p？也是串匹配问题：子串既是目标串，也是模式串，子串的第k（i）个和主串的第i个比较失败，应将子串的哪一个字符继续与主串第i个比较呢？答案：第nextk个！,next的递推计算,2020/5/28,27,第四章串,defgen_next(p):i,k=0,-1next=-1*len(p)#next0=-1whileilen(p)-1:#由nexti计算nexti+1ifk=-1orpi=pk:i,k=i+1,k+1nexti=k#k=-1时，上步计算出了nexti+1=0，即从头比，滑行最远#其他时，计算出了nexti+1=k+1else:k=nextk#k回溯到nextkreturnnext,next的递推计算,2020/5/28,第四章串,28,2020/5/28,第四章串,29,已知next0=-1,nexti=k,求nexti+1=?,a,B,a,x,a,B,a,假设递推过程中求得下一个nexti=k，此时如果pi=pk，则pk与主串的比较必然也是失败的！修正：nexti=nextk,next的不足,2020/5/28,30,第四章串,T=aaaabnext：-10123修正的next：-1-1-1-13T=abaaabcacnext：-100111201修正的next：-10-11102-11,例题：next和修正的next