[POJ3294]Life Forms（后缀数组）

传送门

统计大于一半的串中都出现过的子串，有多个按照字典序输出

二分子串长度 k，用 k 将height 数组分组，接下来直接判断就 ok。

有个小细节，平常统计所有串中都出现的最长子串时，把所有子串拼接起来的符号可以是相同的，但是这个题不行。（为什么？好好想想）

——代码

1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #define N 101001 5 6 int len, n, m, max_num, max_len; 7 int buc[N], x[N], y[N], sa[N], rank[N], height[N], belong[N], pos[N]; 8 char s[N], 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 else if(!f[belong[sa[i]]]) 64 68 return pos[0]; 69 } 70 71 inline void solve() 72 80 if(ans) 81 87 else 88 93 } 94 95 int main() 96 112 len; 113 build_sa(); 114 build_height(); 115 solve(); 116 } 117 return 0; 118 }
View Code

上一篇：[HDU1403]Longest Common Substring（后缀数组）

下一篇：[luoguP3355] 骑士共存问题（二分图最大独立集）

---

后缀数组