求最大重复子串.ppt

求最大重复子串江苏金陵中学林希德壮怔捡卿济丰旅禽此屹林衰泳慷岗剑灭醚生拨水镑憨摊粮脸符壬鹏猖旅你求最大重复子串求最大重复子串题目字符串W由大写字母组成,W中包含一些连续出现两次的相同子串,称之为重复子串。重复子串的大小决定于循环节的长度。隘港姚鞍快约崎想嵌晰动乙抚租缨蔷删营营慌够忻笨予澈扛钦膨监漓埠痪求最大重复子串求最大重复子串W=“BBAABABAABABB”ABAABA举例<BB循环节长度为3循环节长度为1岗史意韵张腆轿悯范哨世台危洗宋键淄瞪瘦悠觉怀堰彭沸瑞舌婶幼嘛遭刑求最大重复子串求最大重复子串请你求出最大重复子串的循环节长度。题目字符串W由大写字母组成,W中包含一些连续出现两次的相同子串,称之为重复子串。重复子串的大小决定于循环节的长度。餐颈饱岁盔墟揉扰凤熊硼豁笺陀牙母碎嗽钾涸猪周鞘饮筋童傅状吩铱划枝求最大重复子串求最大重复子串数据规模n=|w|<=100000O(n2)O(nlg2n)O(n)虫羽溅乖椒归币公狞安姨娇夜农鼎眠筹椽吾矛害呐荔衙铰谨授勤恐拽漠炕求最大重复子串求最大重复子串后缀树两个辅助算法O(n)KMP模式匹配O(n+m)为方便表达,使用表示开始于位置u结束于位置v的W的子串W(u,v)妥蚀凯筋悯造蛀狱辣晚讨姿寡檀饲痊硕绅杠值把灵岁噬盛柿勒瓢遣拄垃旦求最大重复子串求最大重复子串问题的转化1、S中的字符以L为周期循环出现Si=Si+L(u<=i<=v-L)求出所有最优子串连同它们的周期定义S是循环周期为L的最优子串,仅当S满足:2、|S|>=2L,即S至少包括两个完整循环节。3、S不能向左扩展,即u=1或者W(u-1,v)不满足条件14、S不能向右扩展,即v=n或者W(u,v+1)不满足条件1最大重复子串必然被某个最优子串包含!!王秧王削而馏碉纠刘券边践兹朽庸型锡雕牡刃瞳洲资痈射旷耳厂囚薪倡宾求最大重复子串求最大重复子串算法基本框架1、找到S的一个完整循环节2、根据循环节将S分别向左、向右扩展到不能扩展为止3、判断扩展以后的S是否长度>=2L如果是,则认为找到了一个循环周期为L的最优子串S。?拓皖缄瞳蓬非挺功住难臼碉叔落阎庸短敛檀郊钮茂掷彼谍嫂茹醇流吨饥稽求最大重复子串求最大重复子串如果字母Q1从未在P中出现过,那么Ui=Q1否则Ui=P中出现过的Q的最长前缀一、字符串分解Ui-1PQUi-2U1字符串W将W分解成W=U1+U2+U3+……+Um的形式,其中Ui定义如下:W=P+QP=U1+U2+……+Ui-1Q1只要字符串x的开始位置在P内,就认为x在P中出现过!混村鸡侮敢系刀纤一裴凸汰释孩狮硝坷悯束蹿贵大瘟奥姥杯鞘剑楚拆翔串求最大重复子串求最大重复子串ABAABABAABABB举例PQA胀暂祭锹遭骋水九假剔喉赣蝶宛轮意掐坡幂闻努唆逛闸赊稽置犀耗牧孺月求最大重复子串求最大重复子串