传送门

求两个串的公共子串（注意，这个公共子串是连续的一段）

把两个串连在一起，中间再加上一个原字符串中不存在的字符，避免过度匹配。

求一遍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