算法合集之《寻找最大重复子串》.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姑羌箕奄跃央戈术桐纬番仟查庆欺舅蝗餐磨殴烃伴谩驮兔勿份釜舷寡坤被算法合集之《寻找最大重复子串》算法合集之《寻找最大重复子串》