[HDU2328]Corporate Identity（后缀数组）

传送门

求 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

上一篇：[POJ1703]Find them, Catch them（并查集）

下一篇：[CODEVS1911] 孤岛营救问题（分层图最短路）

---

后缀数组