题意
题目链接
sol
用什么后缀数组啊
直接差分之后 二分+hash找最长公共子串就赢了啊。。。
时间复杂度:(o(nlogn))(不过我写的是两个log。。反正也能过)
// luogu-judger-enable-o2 #include<bits/stdc++.h> #define ull unsigned long long using namespace std; const int maxn = 1e6 + 10; const ull base = 27; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, mx; ull po[maxn]; vector<ull> ha[maxn]; vector<int> v[maxn]; map<ull, int> mp, vis; ull getha(int id, int l, int r) { if(l == 0) return ha[id][r]; else return ha[id][r] - ha[id][l - 1] * po[r - l + 1]; } int check(int len) { mp.clear(); for(int i = 1; i <= n; i++) { vis.clear(); for(int j = 0; j < v[i].size() - len + 1; j++) { ull tmp = getha(i, j, j + len - 1); if(!vis[tmp]) vis[tmp] = 1, mp[tmp]++; if(mp[tmp] == n) return 1; } } return 0; } int main() { n = read(); po[0] = 1; for(int i = 1; i <= 10001; i++) po[i] = base * po[i - 1]; for(int i = 1; i <= n; i++) { int num = read(); mx = max(mx, num); for(int j = 1; j <= num; j++) v[i].push_back(read()); for(int j = num - 1; j >= 1; j--) v[i][j] = v[i][j] - v[i][j - 1]; ha[i].reserve(v[i].size() + 1); } for(int i = 1; i <= n; i++) { for(int j = 0; j < v[i].size(); j++) { if(!j) ha[i][j] = 0; else ha[i][j] = (ha[i][j - 1] + v[i][j]) * base; } } int l = 1, r = mx, ans = 0; while(l <= r) { int mid = l + r >> 1; if(check(mid)) ans = mid, l = mid + 1; else r = mid - 1; } cout << ans + 1; return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/606162.html