USACO/theme

 这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。
 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。
 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。

这是USACO Chapter 5 .1中的OI题目Musical Themes的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。

问题分析

算法0 O(n³)

枚举两串的开头，贪心向下找即可（注意优化和重叠）

算法1 O(n⁴)

很直观的想法，就是枚举每一段的头尾，然后找在整个序列中有没有和这一段匹配的（也就是说所有的数都是原来的那一段对应位置的数加一个数或减一个数得到的，题目中有说明）。这样算法的时间复杂度可以达到O(n⁴)。所以这个算法必须进行优化。

1. 如果以i开头的长度为l的序列没有匹配序列，那么比l更长的序列一定不会有解，可以直接跳过。
2. 每次枚举末端那一位时都从开始的一位加上当前最大长度开始枚举。
3. 对于以i开头的序列和以k开头的序列，如果a[i]-a[i+1]<>a[k]-a[k+1]，那么不用judge，直接跳过。

其中优化1的效果是最明显的，优化3次之，优化2的效果最不明显，因为这个太容易想到了…… 加上上述优化，程序就可以过了，但是有点慢。加上二分的效率会更好。

算法2 O(n³)

这个题考虑到相同的旋律之间的差是常数，可以把读入的序列变换一下。就是每个元素与其前一个元素做差。例如原序列 {3,5,7,3,4,4,6,8,4}，做差后是{2,2,-4,1,0,2,2,-4}。这样就可以在变换后的序列中直接查找最长的重复序列即可。上述例子中是2,2,-4，长度为3，对应原序列中3,5,7,3，长度为4。

寻找最长的重复序列，我采用了一种O(N³)的算法。就是枚举两个序列的开头的序列的长度。但对于5000，O(N^3)还是难以过全的。于是采用了一个优化：每次枚举末端那一位时都从开始的一位加上当前最大长度开始枚举，前一个序列开头只用枚举到(N-当前的最大长度)即可。这个优化的力度很大，加上这个优化就全过了，而且很快。

路人癸: 不用任何优化, 直接二分, 利用 O(n³)的算法判定, 最大的点才0.4s. 路人某：刚试过，超了

算法3 O(n²)

时间复杂度也只有O(n²)。但是要在对第一种算法比较深入分析的基础上才可以得出。 显然，一个序列最多只需要一个匹配序列即可，所以我们只需找到这样两个序列。 两层循环，外层循环枚举两个序列开头的位置差（其实也就是每个元素与另一个序列对应元素的位置差），内层循环枚举第一个序列的第一个元素的位置。如果当前位匹配则当前长度加1，否则赋为1。这样，我们可以直接找出合法的序列，并记录最大长度。 这种算法抓住了问题的本质，比第一种算法无论在时间上还是编程复杂度上都降低了不少。

路人R：这似乎就类似于KMP？

或者动态规划

令theme(i,j)表示第一个主题开头为i，第二个主题开头为j所能构成的重复主题的长度

那么有转移方程：

如果note(i+1)-note(i)=note(j+1)-note(j)，则theme(i,j)=them(i+1,j+1)+1,否则theme(i,j)=1(深刻啊)

这个方程需满足 theme(i+1,j+1)+1 <= j-i 否则两主题将会重叠--------dementrock注

路人注释：其实是O（n^3） To 上面的路人：是O(N^2)没错

路人N ：可以直接N次 KMP

路人×： 如果定义theme(i,j)的话，那不是要开5000*5000的数组?这个很大啊！不会爆么？

路人y： 可以用一维数组存，甚至可以不用数组（比如说我写的代码）

路人m：解释一下上面的，用滚动数组存

路人y：可以滚动数组都不用，只用一个变量维护max值

算法4 O(n²lgn)

二分(lg(n))，然后枚举开头用KMP判断子串(O(N^2)/2) //杯具的小菜飘过。。居然这样超时，，，RP太差。。

算法5 O(nlogn)

1.利用算法二的想法，也就是当成串来匹配。

2.假如已经知道长度d存在 那可以利用哈希表，扫过一次整个数组(O(n))，如果前面出现过，代表有重复。

※需要注意的是，两个可匹配串之间必须至少有一个其它元素。

3.对于长度d去做二分搜(O(logn))

因为若长度d存在重复旋律 那对于长度e<d必也存在重复旋律。

故总复杂度O(nlogn)

//USACO对内存的限制比较狠,所以需要Hash冲突问题

算法6 O(nlogn)

计算做差，然后用后缀数组求最长重复子串。

用二分答案法对height数组进行分组。O(nlogn)。全部0.00s。 stjz

路人m：后缀树貌似有O(n)的方法

算法7 O(n²)

我用的O（n^2）的DP，F[I][J]为第I个与第J个匹配时的最大值

方程：F[I][J]=MAX(F[I][J],F[I-1][J-1]+1) (A[I]-A[J]==A[I-1]-A[J-1])

答案就是所有F[I][J]的最大值，最大值在求的时候顺便算出就行了

然后用滚动数组优化一下空间就可以AC，时间还可以，最慢的是0.17s。。。

路人：数据二有重叠的情况，须判 f[(i+1)%2][j-1]+1<=j-i

路人丙子：这个算法其实就是最长连续公共子序列。数组原地滚动即可(第二重循环逆序)。由于是自匹配，所以计算出的矩阵是沿对角线对称的（加上这一条每个点就都在0.1s以内了~）。

算法8 O(n)

对原序列求前后差，得一新序列

用O(n)的时间建立该序列的后缀树

重复子串=两后缀的公共前缀

只要找树的一条链的一个叶子（就是元素为结束符的节点） 标明深度D1。再回溯找到一个分叉，记录出深度D2，如果D2<=D1/2，则某一个重复序列的长度为D2，否则为D2-D1（这一段就是避免重复的），同样处理这个分叉上的叶节点以此类推，处理完后继续回溯。为了使算法时间复杂度更低，压缩单链节点是必要的（但深度还是得记录为原树的深度），否则复杂度退化为O(n²)。

当然要特殊处理最终答案小于5的情况。

有错误请指出（打完后立即觉得似乎有...）。

算法9

先按照前后的差值来更新为N-1长数列，同时把相同值的位置分散在同一个VECTOR内，接下来只要对每一个VECTOR进行O(N^3)的比较即可，最慢的0.07就过了，主要是写起来很方便

参考代码

C

C++

Pascal

Java