传送门
求出现超过1次的不重叠子串的个数
根据论文中的方法。
枚举子串的长度 k。
用 k 给 height 数组分组，每一组求解，看看当前组的位置最靠后的后缀和位置最靠前的后缀所差个数是否大于长度，大于的话 ans++。
分组思想需要认真体会一下。
——代码
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define N 1005 5 #define max(x, y) ((x) > (y) ? (x) : (y)) 6 #define min(x, y) ((x) < (y) ? (x) : (y)) 7 8 int len, n, m, ans; 9 int buc[N], x[N], y[N], sa[N], ran[N], height[N]; 10 char s[N]; 11 12 inline void build_sa() 13 35 } 36 37 inline void build_height() 38 49 } 50 51 inline void check(int k) 52 61 else 62 66 ans += Max Min >= k; 67 } 68 69 int main() 70 82 return 0; 83 }View Code
上一篇：[luoguP1879] [USACO06NOV]玉米田Corn Fields（DP）
下一篇：[luoguP2763] 试题库问题（最大流）
后缀数组
