求最大重复子串求最大重复子串江苏金陵中学林希江苏金陵中学林希德德题目题目字符串W由大写字母组成，W中包含一些连续出现两次的相同子串，称之为重复子串
重复子串的大小决定于循环节的长度
W=“BBAABABAABABB”ABAABA举例举例=红色线段矛盾，情况c也不存在
SS的开始位置不能太早的开始位置不能太早这里又一次用到了字符串分解的定义重要结论重要结论111
S的开始位置早于Ui且最末循环节没有将Ui-1包含在内，故L=L最优子串SUi实际就是Ｓ的一个完整循环节U(1,L)这个结论很重要
找到循环节了
VU最优子串S1、尽量向右扩展三、循环节扩展和长度判定三、循环节扩展和长度判定完整循环节2、尽量向左扩展3、如果扩展以后的|S|>=2L，那么S是最优子串
U(1,L)实际就是Ｓ的一个完整循环节找到循环节了
BBAABABAABABB举例举例VU寻找循环周期为5的最优子串完整循环节举例举例BBAABABAABABBVU寻找循环周期为5的最优子串完整循环节举例举例BBAABABAABABBVU寻找循环周期为5的最优子串完整循环节举例举例BBAABABAABABBVU结束位置寻找循环周期为5的最优子串完整循环节举例举例BBAABABAABABBVU寻找循环周期为5的最优子串完整循环节结束位置举例举例BBAABABAABABBVU寻找循环周期为5的最优子串完整循环节结束位置举例举例BBAABABAABABBVU
