[POJ1226]Substrings（后缀数组）

传送门

给定 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

上一篇：[HDU3518]Boring counting（后缀数组）

下一篇：[luoguP2024] 食物链（并查集）

---

后缀数组