P7180 [BOI2004] REPEATS

D2T1 · 2023-09-20 21:05:46 · 题解

P7180 [BOI2004] REPEATS

题意：给定字符串，求重复次数最多的连续重复子串。

考虑枚举这个子串的长度 k。如果 lcp(suf(i), suf(i+k))=x，那么则 s_{[i,i+k-1]} 重复了 \lfloor \dfrac{x}{k}\rfloor 次。那么我们就得到了一个 O(n^2) 的做法，即先枚举 k，再枚举 i。

考虑优化，其实我们并不需要枚举所有的 i。容易发现如果 [i,i+k-1] 与 [j,j+k-1] 有交的话，计算一个向两侧的 lcp 即可。具体地，若计算 i，令 l=i-1-lcs(pre(i+k-1), pre(i-1))+1，r=i+k+lcp(suf(i), suf(i+k))-1，答案用 \lfloor \dfrac{r-l+1}{k}\rfloor 更新。这样我们只用枚举 i=1,1+k,1+k*2,...。

lcp 和 lcs（反串 lcp）可使用后缀数组求解。

复杂度为 O(n\log n+\dfrac n1 +\dfrac n2+...+\dfrac nn)=O(n\log n)。

//P7180
#include <bits/stdc++.h>
using namespace std;

const int N = 5e4 + 10;
int t, n, a[N], lg2[N];
int sa[N], rk[N], cn[N], pr[N], he[N];
int st[N][20], stt[N][20];
int saa[N], rkk[N], hee[N];

void initial(){
    memset(sa, 0, sizeof(sa));
    memset(rk, 0, sizeof(rk));
    memset(cn, 0, sizeof(cn));
    memset(pr, 0, sizeof(pr));
    memset(he, 0, sizeof(he));
}
void suftech(){
    int m = 26;
    for(int i = 1; i <= n; ++ i){
        rk[i] = a[i];
        ++ cn[rk[i]];
    }
    for(int i = 2; i <= m; ++ i){
        cn[i] += cn[i-1];
    }
    for(int i = n; i >= 1; -- i){
        sa[cn[rk[i]]--] = i;
    }
    for(int k = 1; k <= n; k <<= 1){
        int tot = 0;
        for(int i = n - k + 1; i <= n; ++ i){
            pr[++tot] = i;
        }
        for(int i = 1; i <= n; ++ i){
            if(sa[i] > k){
                pr[++tot] = sa[i] - k;
            }
        }
        for(int i = 1; i <= m; ++ i){
            cn[i] = 0;
        }
        for(int i = 1; i <= n; ++ i){
            ++ cn[rk[i]];
        }
        for(int i = 2; i <= m; ++ i){
            cn[i] += cn[i-1];
        }
        for(int i = n; i >= 1; -- i){
            sa[cn[rk[pr[i]]]--] = pr[i];
            pr[i] = 0;
        }
        swap(rk, pr);
        tot = 1;
        rk[sa[1]] = 1;
        for(int i = 2; i <= n; ++ i){
            if(pr[sa[i]] == pr[sa[i-1]] && pr[sa[i]+k] == pr[sa[i-1]+k]){
                rk[sa[i]] = tot;
            } else {
                rk[sa[i]] = ++ tot;
            }
        }
        if(tot == n){
            break;
        }
        m = tot;
    }
    int k = 0;
    for(int i = 1; i <= n; ++ i){
        if(rk[i] == 1){
            he[rk[i]] = 0;
        }
        if(k){
            -- k;
        }
        int j = sa[rk[i]-1];
        while(i+k <= n && j+k <= n && a[i+k] == a[j+k]){
            ++ k;
        }
        he[rk[i]] = k;
    }

    for(int i = 1; i <= n; ++ i){
        st[i][0] = he[i];
    }
    for(int i = 1; i <= lg2[n]; ++ i){
        for(int j = 1; j + (1<<i) - 1 <= n; ++ j){
            st[j][i] = min(st[j][i-1], st[j+(1<<(i-1))][i-1]);
        }
    }
}

int ask(int l, int r){
    if(l > r){
        swap(l, r);
    }
    ++ l;
    int k = lg2[r - l + 1];
    return min(st[l][k], st[r-(1<<k)+1][k]);
}
int askk(int l, int r){
    if(l > r){
        swap(l, r);
    }
    ++ l;
    int k = lg2[r - l + 1];
    return min(stt[l][k], stt[r-(1<<k)+1][k]);
}

int main(){
    lg2[0] = -1;
    for(int i = 1; i <= 50000; ++ i){
        lg2[i] = lg2[i>>1] + 1;
    }
    scanf("%d", &n);
    int ans = 0, lee, stp;
    for(int i = 1; i <= n; ++ i){
        static char ch[5];
        scanf("%s", ch);
        a[i] = ch[0] - 'a' + 1;
    }
    initial();
    suftech();
    reverse(a + 1, a + n + 1);
    memcpy(stt, st, sizeof(st));
    memcpy(saa, sa, sizeof(sa));
    memcpy(rkk, rk, sizeof(rk));
    memcpy(hee, he, sizeof(he));
    initial();
    suftech();
    for(int len = 1; len <= n; ++ len){
        for(int st = 1; st + len - 1 <= n; st += len){
            int r = st + len + askk(rkk[st], rkk[st+len]) - 1;
            int l = st - 1 - ask(rk[n-(st+len-1)+1], rk[n-(st-1)+1]) + 1;
            if(ans < (r-l+1) / len){
                ans = (r-l+1) / len;
                lee = len;
                stp = l;
            }
        }
    }
    printf("%d\n%d\n%d\n", ans, lee, stp);
    return 0;
}