[FZU1540 迎接光棍节]枚举+KMP Or 二分+后缀数组

【题目】多串的最长等差连续子串。中文题目：http://acm.fzu.edu.cn/problem.php?pid=1540

【算法分析】

这个作为后缀数组的经典例题之一。。。就不用说了。。。

但是很囧的是，我写的后缀数组MLE了= =。由于我的后缀数组特别搓，所以套模板的人们应该都可以过。

注意到这题的特殊性，n<=4000，每个串长<=200。

所以可以有一个暴力解法。

先等差处理。(a[i]-a[i-1])

然后枚举答案在串1中开始的位置。

于是以第一个串从枚举的开始位置到第一个串末端作为模式串。

去和n-1个串暴力KMP匹配。可以得到最多能配多长。

然后就能过了。

【时间复杂度】O(Len*Sum) Len为第一个串的长度。Sum为所有串的字母数之和。

【空间复杂度】O(Sum)

【CODE】

#include