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

串与模式匹配2016Fall《数据结构》2020/5/241第四章串文本……字符串的应用？？？2020/5/24第四章串2求串长取子串定位子串（串匹配）子串替换两个串的连接…串的常用操作2020/5/24第四章串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/24第四章串4顺序存储静态数组动态数组块链存储链式，每个结点存储一定长度的子串串的存储表示2020/5/245第四章串#defineMAXSTRLEN255typedefunsignedcharSString[MAXSTRLEN+1];//用户可在255以内定义最大串长,//超过予定义长度的串值则被舍去，称之为“截断”;//0号单元存放串的长度顺序存储表示——静态数组2020/5/246第四章串typedefstruct{char*ch;//按串长分配存储区intlength;//串长度}HString;顺序存储表示——动态数组2020/5/247第四章串#defineCHUNKSIZE80//块大小typedefstructChunk{charch[CUNKSIZE];structChunk*next;}Chunk;typedefstruct//串的链表结构Chunk*head,*tail;//串的头和尾指针intcurlen;//串的当前长度}LString;块链存储表示abcdefh##^headabcd^head2020/5/248第四章串str是不变类型对象创建后，内容（和长度）不变采用顺序存储表示——动态数组Python字符串类型str其他长度len串内容存储区...串匹配与KMP算法2020/5/2410第四章串许多计算机应用的最基本操作是字符串匹配。如用编辑器或字处理系统工作时，在文本中查找单词或句子（中文字或词语），在程序里找拼写错误的标识符等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=t0t1t2…tn-1称为主串（目标串）p=p0p1p2…pm-1称为子串（模式串）通常有mn串匹配（模式匹配）——子串定位2020/5/24第四章串13defnaïve_matching(t,p):j,i=0,0whilejlen(t)andilen(p):ift[j]==p[i]:j,i=j+1,i+1else:#不同时，j回溯，i回到头j,i=j-i+1,0ifi==len(p):returnj-ireturn-1朴素的串匹配算法2020/5/24第四章串14朴素的串匹配算法000010000000000001ji2020/5/2415第四章串每次匹配失败时，j回溯到i-j+1，i回溯到0效果：模式每次向前滑动一步，从头比较；时间复杂度：O（n*m）例：t50=000…0001，p5=00001比较次数：(50-5)*5+5=(n-m+1)*m=O(n*m)算法的缺陷2020/5/2416第四章串是一个高效串匹配算法时间复杂度：O(n+m)由D.E.Knuth和V.R.Pratt提出，J.H.Morris几乎同时发现，因此称KMP算法。KMP算法2020/5/24第四章串17KMP算法示意图abcacababcabcacbabji2020/5/2418第四章串思想：当t[j]!=p[i]时，j指针不回溯，i回溯到next[i]，让t[j]与p[next[i]]继续比较；效果：模式向前滑动i-next[i]步，从next[i]处开始比较，next[i]越小，滑动越远！KMP算法2020/5/2419第四章串defmatching_KMP(t,p,next):j,i=0,0whilejlen(t)andilen(p):ifi==-1ort[j]==p[i]:j,i=j+1,i+1else:i=next[i]#只i回溯到next[i]，即不动#i回溯相当于子串向前滑动，#让子串的第next[i]继续与主串的第j个比较ifi==len(p):returnj-ireturn-1KMP算法2020/5/24第四章串20next[i]=k的直观刻画abcbabcaacabcbabcaacikabcabcabcp[0..i-1]的最长的、前缀、后缀的真子串的长度2020/5/2421第四章串next[i]表示子串的第i个和主串的第j个比较失败，让子串的第next[i]继续与主串的第j个比较若第0个比较就失败，则主串应该换到下一位置，和子串从头开始比较；若认为j不动，则相当于主串的第j个和子串的-1位置在比较next的定义2020/5/24第四章串22next[i]=-串长其他10串：p[0..i-1]的最长的、前缀、后缀、真子串；空串时，串长为0i1时，next[i]=“串长”串：p[0..i-1]的最长的、前缀、后缀、真子串•最长：不能推得太远；•前缀：由前推过来；•后缀：对齐；•真子串：至少向前滑一步；可以是空串，此时串长为零。i=1时，next[1]=0【上面Case的特殊情形】p[0..1-1]=p[0]没有真字串，则前后缀串也是空串直接：p[1]与t[j]比较失败，则应让p[0]与t[j]继续比较i=0时，next[0]=-1p[0]与t[j]比较失败，此时i、j指针应同时后移，让p[0]与t[j+1]去比若认为j不动，则p[-1]在和t[j]“对齐”next的定义2020/5/2423第四章串T=aaaabnext：-10123T=abaaabcacnext：-100111201例：利用“最长前后缀串”方法求next2020/5/2424第四章串“递推”利用已知的计算结果：next[0]，…，next[i]，来求next[i+1]next的递推计算2020/5/2425第四章串已知next[0]=-1,…,next[i]=k,求next[i+1]=?abcaabcaBcabcaabcaBcabcxabcaBcabcxabcaBcaBaxaBa2020/5/2426第四章串设next[i]=k若：p[i]==p[k]，则：next[i+1]=k+1若：p[i]!=p[k]，则需往后回朔，检查p[i]==p[？]•也是串匹配问题：子串既是目标串，也是模式串，•子串的第k（i）个和主串的第i个比较失败，应将子串的哪一个字符继续与主串第i个比较呢？•答案：第next[k]个！next的递推计算2020/5/2427第四章串defgen_next(p):i,k=0,-1next=[-1]*len(p)#next[0]=-1whileilen(p)-1:#由next[i]计算next[i+1]ifk==-1orp[i]==p[k]:i,k=i+1,k+1next[i]=k#k=-1时，上步计算出了next[i+1]=0，即从头比，滑行最远#其他时，计算出了next[i+1]=k+1else:k=next[k]#k回溯到next[k]returnnextnext的递推计算2020/5/24第四章串28已知next[0]=-1,…,next[i]=k,求next[i+1]=?abcaabcaBcabcaabcaBcabcxabcaBcabcxabcaBcaBaxaBa2020/5/2429第四章串假设递推过程中求得下一个next[i]=k，此时如果p[i]=p[k]，则p[k]与主串的比较必然也是失败的！修正：next[i]=next[k]next的不足2020/5/2430第四章串T=aaaabnext：-10123修正的next：-1-1-1-13T=abaaabcacnext：-100111201修正的next：-10-11102-11例题：next和修正的next2020/5/2431第四章串defgen_next(p):i,k=0,-1next=[-1]*len(p)whileilen(p)-1:ifk==-1orp[i]==p[k]:i,k=i+1,k+1ifp[i]==p[k]:next[i]=next[k]else:next[i]=kelse:k=next[k]returnnext对next的修正2020/5/24第四章串32