poj1743专题

POJ1743——不可重迭的最长重复子串

题意:给定一系列的整数作为音阶,旋律为相邻音阶之差。问最长的主旋律是多长,主旋律需满足3个条件: 1. 长度至少为5; 2. 至少重复出现2次; 3. 主旋律各不重迭。 对源进行变换以后,就是问不重迭的最长重复子串是多长。求出SA数组与Height数组以后。 首先将问题改为判定性问题,即给定长度L,问是否存在L长度的不重迭重复子串。其等价于在Height数组中找到一个区间[i,j],He