传送门
给定 n 个字符串，求出现或反转后出现在每个字符串中的最长子串。
算法分析:
这题不同的地方在于要判断是否在反转后的字符串中出现。其实这并没有加大题目的难度。
只需要先将每个字符串都反过来写一遍，中间用一个互不相同的且没有出现在字符串中的字符隔开，
再将 n 个字符串全部连起来，中间也是用一个互不相同的且没有出现在字符串中的字符隔开，求后缀数组。
然后二分答案，再将后缀分组。
判断的时候，要看是否有一组后缀在每个原来的字符串或反转后的字符串中出现。
这个做法的时间复杂度为 O(nlogn)。
——代码
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define N 21001 5 6 int len, n, m, max_num, T; 7 int buc[N], x[N], y[N], sa[N], rank[N], height[N], belong[N], s[N]; 8 char a[N]; 9 bool f[101]; 10 11 inline void build_sa() 12 34 } 35 36 inline void build_height() 37 48 } 49 50 inline bool check(int k) 51 62 else if(height[i] < k) 68 return 0; 69 } 70 71 inline int solve() 72 80 return ans; 81 } 82 83 int main() 84 103 len; 104 build_sa(); 105 build_height(); 106 if(n == 1) 107 111 printf("%d\n", solve()); 112 } 113 return 0; 114 }View Code
上一篇：[BZOJ1030] [JSOI2007]文本生成器（AC自动机 + DP）
下一篇：[luoguP3355] 骑士共存问题（二分图最大独立集）
后缀数组
