c/c++语言开发共享BZOJ4698: Sdoi2008 Sandy的卡片(二分 hash)

题意

题目链接

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; }