锦州网站制作,软件著作权交易平台,聊城做网站的公司新闻,wordpress招商题目链接 \(Click\) \(Here\) 真的好麻烦啊。。事实证明#xff0c;理解是理解#xff0c;一定要认认真真把板子打牢#xff0c;不然调锅的时候真的会很痛苦。。#xff08;最好是八分钟能无脑把\(SA\)码对的程度\(QAQ\)#xff09; 这个题最开始我想的是\(RMQ\)遍历每一个…题目链接 \(Click\) \(Here\) 真的好麻烦啊。。事实证明理解是理解一定要认认真真把板子打牢不然调锅的时候真的会很痛苦。。最好是八分钟能无脑把\(SA\)码对的程度\(QAQ\) 这个题最开始我想的是\(RMQ\)遍历每一个子区间但是意识到复杂度是\(O(N^2)\)然后就\(GG\)了。怎么说呢后缀数组和二分似乎是很常见的组合和莫队也是这个题只需要在\(height\)数组里二分\(lcp\)长度即可\(check\)函数里面处理一下要让区间内所有原串都有至少一个子串。 #include bits/stdc.h
using namespace std;const int N 200010;int s[N], id[N];
int n, m, num, len, tot 10000;
int sa[N], tp[N], rk[N], _rk[N], bin[N], height[N];void get_height (int n) {int k 0;for (int i 1; i n; i) {if (k ! 0) k--;int j sa[rk[i] - 1];while (s[i k] s[j k]) k;height[rk[i]] k;}
}void base_sort (int n, int m) {for (int i 0; i m; i) bin[i] 0;for (int i 1; i n; i) bin[rk[tp[i]]];for (int i 1; i m; i) bin[i] bin[i - 1];for (int i n; i 1; --i) sa[bin[rk[tp[i]]]--] tp[i];
}void suffix_sort (int n, int m) {for (int i 1; i n; i) {rk[i] s[i];tp[i] i;}base_sort (n, m);for (int w 1; w n; w 1) {int cnt 0;for (int i n - w 1; i n; i) {tp[cnt] i;}for (int i 1; i n; i) {if (sa[i] w) {tp[cnt] sa[i] - w;}}base_sort (n, m);memcpy (_rk, rk, sizeof (rk));rk[sa[1]] cnt 1;for (int i 2; i n; i) {rk[sa[i]] _rk[sa[i]] _rk[sa[i - 1]] _rk[sa[i] w] _rk[sa[i - 1] w] ? cnt : cnt;}if (cnt n) break;m cnt;}
}bool vis[1010]; int sta[N], top 0;bool can_use (int l) {while (top) vis[sta[top--]] false;for (int i 1; i len; i) {if (height[i] l) {while (top) vis[sta[top--]] false;}if (!vis[id[sa[i]]]) {vis[id[sa[i]]] true;sta[top] id[sa[i]];if (top n) return true;}}return false;
}int main () {cin n;int ban 2000;for (int i 1; i n; i) {cin m;for (int j 1; j m; j) {cin s[len]; //把所有的字符串整合到一个里id[len] i; // 表明主权len号后缀的lcp属于串i}s[len] ban; //隔开}for (int i len; i 1; --i) {s[i] s[i] - s[i - 1] 4000;}suffix_sort (len, 10000);get_height (len);int l 0, r len;while (l r) {int mid (l r 1) 1;if (can_use (mid)) {l mid;} else {r mid - 1;}}cout l 1 endl;
}转载于:https://www.cnblogs.com/maomao9173/p/10438209.html
