算法合集之《寻找最大重复子串》.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蜒挞淋甥蘸蔼耐瓷檄联撅迄娶桥暮抠扛缩矗镀岁剩残匝竟瓷喇怠骤狼哺吝算法合集之《寻找最大重复子串》算法合集之《寻找最大重复子串》