传送门
求 n 个串的字典序最小的最长公共子串。
和 2 个串的处理方法差不多。
把 n 个串拼接在一起，中间连上一个没有出现过的字符防止匹配过界。
求出 height 数组后二分公共子串长度给后缀数组分组。
然后 check，每一组中是否所有的字符串都包含。
直接遍历 sa 数组，第一个满足的结果就是字典序最小的。
——代码
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define N 900005 5 #define M 1 6 7 int n, len, m, start; 8 int buc[N], x[N], y[N], sa[N], rank[N], height[N], belong[N]; 9 char s[N], a[M]; 10 bool f[M]; 11 12 inline void build_sa() 13 35 } 36 37 inline void build_height() 38 49 } 50 51 inline bool check(int k) 52 66 } 67 else 68 73 return 0; 74 } 75 76 int main() 77 91 len; 92 build_sa(); 93 build_height(); 94 for(i = 1; i < len; i++) belong[i] += belong[i 1]; 95 l = 1, r = len, leng = 0, start = 1; 96 while(l <= r) 97 102 if(leng && start ^ 1) 103 107 else puts("IDENTITY LOST"); 108 } 109 return 0; 110 }View Code
上一篇：[luoguP2758] 编辑距离（DP）
下一篇：[luoguP2770] 航空路线问题（最小费用最大流）
后缀数组
