传送门
求两个串的公共子串（注意，这个公共子串是连续的一段）
把两个串连在一起，中间再加上一个原字符串中不存在的字符，避免过度匹配。
求一遍height，再从height中找满足条件的最大值即可。
为什么只需要相邻两字典序的后缀呢？因为字典序相邻公共前缀一定最大。
——代码
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define N 200005 5 #define max(x, y) ((x) > (y) ? (x) : (y)) 6 7 int len, n, ans, m = 'z' + 1; 8 int buc[N], x[N], y[N], sa[N], rank[N], height[N]; 9 char s[N]; 10 11 inline void build_sa() 12 34 } 35 36 inline void build_height() 37 48 } 49 50 int main() 51 67 return 0; 68 }View Code
上一篇：[luoguP2854] [USACO06DEC]牛的过山车Cow Roller Coaster（DP + sort）
下一篇：[luoguP2766] 最长递增子序列问题（最大流）
后缀数组
