[BZOJ4698]Sdoi2008 Sandy的卡片（字尾數組+二分答案）

Address

https://www.lydsy.com/JudgeOnline/problemset.php?search=SDOI2008

Solution

首先我們發現，相同的定義「兩個子串長度相同且一個串的全部元素加上一個數就會變成另一個串」不好處理。

是以考慮将每張卡片的字元序列差分，即将原來一個長度為 m m 的串變成一個長度為 m−1m−1 的串，第 i i 個字元為原來第 i+1i+1 個字元和第 i i 個字元之差。

這樣，我們就隻需要求出這些字元串的最長公共子串，然後加一就得到答案。

這是字尾數組的經典應用。

先把這 nn 個串用一個無關的字元順次連接配接起來，對這個連接配接起來的串求 height h e i g h t 數組，這樣就把公共字首轉成了區間最小值。

容易得到：

n n 個串存在一個長度為 midmid 的公共子串，當且僅當 height h e i g h t 存在一個區間 [l,r] [ l , r ] 滿足區間最小值 ≥mid ≥ m i d 且對于 n n 個串中的每一個串 SS 都滿足：存在一個 i∈[l−1,r] i ∈ [ l − 1 , r ] 滿足 sa[i] s a [ i ] 在連接配接起來的串中的對應位置屬于 S S 。

我們二分 midmid ，判定時将 height h e i g h t 中 ≥mid ≥ m i d 的值标記出來，取出被标記的連續區間判斷即可。

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, a, b) for (i = a; i <= b; i++)
#define Rof(i, a, b) for (i = a; i >= b; i--)
#define Pow(k, n) for (k = 1; k < n; k <<= 1, swap(x, y))
using namespace std;
inline int read() {
    int res = ; bool bo = ; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = ; else res = c - ;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << ) + (res << ) + (c - );
    return bo ? ~res +  : res;
}
const int N = , M =  + ;
int num, m[N], val[N][N], n, s[M], sa[M], rank[M], height[M], w[M], bel[M];
bool vis[M], siv[N];
void cyxisdalao() {
    int i, k, m = , *x = rank, *y = height;
    For (i, , n) w[x[i] = s[i]]++;
    For (i, , m) w[i] += w[i - ];
    For (i, , n) sa[w[x[i]]--] = i;
    Pow(k, n) {
        int tt = ;
        For (i, n - k + , n) y[++tt] = i;
        For (i, , n) if (sa[i] > k) y[++tt] = sa[i] - k;
        memset(w, , sizeof(w));
        For (i, , n) w[x[i]]++;
        For (i, , m) w[i] += w[i - ];
        Rof (i, n, ) sa[w[x[y[i]]]--] = y[i];
        m = ;
        For (i, , n) {
            int u = sa[i], v = sa[i - ];
            y[u] = x[u] != x[v] || x[u + k] != x[v + k] ? ++m : m;
        }
        if (m == n) break;
    }
    if (y != rank) copy(y, y + n + , rank);
    k = height[] = ;
    For (i, , n) {
        if (k) k--;
        int x = sa[rank[i] - ];
        while (s[x + k] == s[i + k]) k++;
        height[rank[i]] = k;
    }
}
bool check(int mid) {
    int i, j;
    For (i, , n) vis[i] = height[i] >= mid;
    for (int i = ; i <= n;) {
        if (!vis[i]) {i++; continue;}
        int nxt = i;
        while (nxt <= n && vis[nxt]) nxt++;
        int cnt = ;
        For (j, i - , nxt - ) if (bel[sa[j]] && !siv[bel[sa[j]]])
            siv[bel[sa[j]]] = , cnt++;
        For (j, i - , nxt - ) siv[bel[sa[j]]] = ;
        if (cnt == num) return ;
        i = nxt;
    }
    return ;
}
int main() {
    int i, j;
    num = read();
    For (i, , num) {
        m[i] = read();
        For (j, , m[i]) val[i][j] = read();
        For (j, , m[i]) s[++n] = val[i][j] - val[i][j - ] + ,
            bel[n] = i;
        s[++n] = ;
    }
    cyxisdalao();
    int l = , r = ;
    while (l <= r) {
        int mid = l + r >> ;
        if (check(mid)) l = mid + ;
        else r = mid - ;
    }
    cout << r +  << endl;
    return ;
}