Openjudge原題鏈接

• 題意
  輸入一個(gè)長(zhǎng)度N(<=20000)的數(shù)組窘疮，求出其重復(fù)K次的最長(zhǎng)可重疊子串
• 思路
  由于N可以達(dá)到20000，故考慮O(NlogN)的算法，于是想到后綴數(shù)組。
  假設(shè)取出了數(shù)組的全部后綴端姚，那么重復(fù)K次的最長(zhǎng)可重疊子串就是在全部后綴中出現(xiàn)K次的最長(zhǎng)前綴。所以需要將后綴用倍增方法排序挤悉，并計(jì)算出相鄰串的公共前綴長(zhǎng)度（h數(shù)組）渐裸，用RMQ分別查找[1...K],[2...K+1]...[N-K...N-1]的區(qū)間最小值，最大的一個(gè)就是重復(fù)了K次的可重疊子串長(zhǎng)度装悲。
• 難點(diǎn)在于求后綴數(shù)組和使用RMQ昏鹃。
• 后綴數(shù)組的求法：sa[i]表示排第i的字符串是哪個(gè)，用rk[i] 第i個(gè)字符串排第幾（相同的字符串有一樣的排名）衅斩。根據(jù)所有后綴的前n個(gè)字符計(jì)算出rk數(shù)組盆顾，根據(jù)rk數(shù)組更新sa數(shù)組。然后根據(jù)后綴的前2n個(gè)字符計(jì)算出新的rk數(shù)組.
  為什么可以這樣做呢畏梆？因?yàn)?strong>suffix(i,2n)=suffix(i,n)+suffix(i+n,n)您宪。
  故前2n個(gè)字符的排名可以看成2元組(rk[i],rk[i+n])。用這個(gè)二元組進(jìn)行排序即可奠涌。
  這樣宪巨，每次計(jì)算rk和sa是O(n)的時(shí)間，而一共進(jìn)行了O(logn)趟溜畅，故計(jì)算rk和sa耗時(shí)O(nlogn)捏卓。
• 然后，求h數(shù)組 h[k]=LCP(suffix[sa[k]],suffix[sa[k+1]])慈格，這時(shí)候再一次利用后綴字符串的性質(zhì)怠晴。
  假設(shè)我們已經(jīng)求得h[k]=LCP(suffix[sa[k]],suffix[sa[k+1]]),假設(shè)sa[k]=i,sa[k+1]=j遥金。
  那么LCP(suffix(i+1),suffix(j+1))=max(h[k]-1,0).找到i+1在sa中的位置t(t=rk(i+1)),sa[t+1]=p.
  即h[t]=LCP(suffix(i+1),suffix(p))
  而suffix(i)<suffix(j) => suffix(i+1)<suffix(j+1)
  而suffix(p)緊鄰suffix(i+1)，故有
  suffix(i+1)<suffix(p)<=suffix(j+1)
  所以有h[t]>=max(h[k]-1,0),繼續(xù)匹配則得到h[t]
• RMQ是一種用O(nlogn)時(shí)間預(yù)處理蒜田，O(1)時(shí)間求區(qū)間最小值的數(shù)據(jù)結(jié)構(gòu)稿械，用dp實(shí)現(xiàn)，其空間復(fù)雜度為O(nlogn)冲粤。
  用dp[i][j]表示[i,i+2^j-1]的區(qū)間最小值美莫，那么轉(zhuǎn)移方程就是
  dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1])
  那么為了查詢區(qū)間[l,r]的最小值，只需要找到最大的k,s.t. (1<<k)<=(r-l+1)梯捕，則
  ans=min(dp[l][k],dp[r-(1<<k)+1][k].要注意這里的邊界條件.
• AC代碼

/*
    輸入一個(gè)長(zhǎng)度N(<=20000)的數(shù)組厢呵，求出其重復(fù)K次的最長(zhǎng)可重疊子串
    由于N可以達(dá)到20000，故考慮O(NlogN)的算法傀顾，于是想到后綴數(shù)組襟铭。
    假設(shè)取出了數(shù)組的全部后綴，那么重復(fù)K次的最長(zhǎng)可重疊子串就是在全
    部后綴中出現(xiàn)K次的最長(zhǎng)前綴锣笨。所以需要將后綴用倍增方法排序蝌矛，并計(jì)
    算出相鄰串的公共前綴長(zhǎng)度（h數(shù)組），用RMQ分別查找[1...K],
    [2...K+1]...[N-K...N-1]的區(qū)間最小值错英，最大的一個(gè)就是重復(fù)了K
    次的可重疊子串長(zhǎng)度。
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
const int N = 1e5+5;
const int LOGN = 20;
const int M = 1e6 + 5;
int a[N], sa[N], rk[N], h[N];// sa[i] 排第i的字符串是哪個(gè); rk[i] 第i個(gè)字符串排第幾
int cnt[M];
int t1[N], t2[N];//tmp array
int dp[N][LOGN];
int n, K;
void build_sa(int* s) {
    memset(cnt, 0, sizeof(cnt));
    int m = 0;
    for (int i = 1; i <= n; i++) {
        m = max(m, a[i]);//m for max
        cnt[s[i]]++;
        t1[i] = s[i];
    }
    for (int i = 1; i <= m; i++) {
        cnt[i] += cnt[i - 1];
    }
    int t = 1;
    for (int i = 1; i <= n; i++) {
        rk[i] = cnt[t1[i]];
    }
    for (int i = 1; i <= n; i++) {
        sa[cnt[t1[i]]--] = i;//初始化sa
    }
    /*a[0] = -1;
    for (int i = 1; i <= n; i++) {//初始化rk
        if (a[sa[i]] != a[sa[i - 1]])
            rk[sa[i]] = rk[sa[i - 1]] + 1;
        else rk[sa[i]] = rk[sa[i - 1]];
    }*/

    for (int k = 1; k <= n; k <<= 1)
    {
        int p = 0;
        for (int i = n - k + 1; i <= n; i++) t2[++p] = i;
        for (int i = 1; i <= n; i++) if (sa[i] > k) t2[++p] = sa[i] - k;

        for (int i = 0; i <= m; i++) cnt[i] = 0;
        for (int i = 1; i <= n; i++) cnt[t1[i]]++;
        for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
        /* 雙關(guān)鍵字排序 */
        for (int i = n; i >= 1; i--) sa[cnt[t1[t2[i]]]--] = t2[i];//wtf,根據(jù)rk(t1)更新sa,但這到底是在做什么Ｂ”椭岩！

        for (int i = 1; i <= n; i++) swap(t1[i], t2[i]);//t2記錄原先的t1
        p = 0; t1[sa[1]] = ++p;
        /* 計(jì)算t1為新的rk，即以前2^k個(gè)字符排序得到的rk */
        for (int i = 2; i <= n; i++)
            t1[sa[i]] = (t2[sa[i]] == t2[sa[i - 1]] &&
                t2[sa[i] + k] == t2[sa[i - 1] + k]) ? p : ++p;
        m = p; if (m >= n) break;//優(yōu)化策略
    }

    for (int i = 1; i <= n; i++) rk[sa[i]] = i;
    /* 根據(jù) rk,sa 計(jì)算h數(shù)組 */
    /* h[k]=LCP(suffix[sa[k-1]],suffix[sa[k]]) */
    int p = 0;
    for (int i = 1; i <= n; i++)
    {
        if (rk[i] == 1) p = 0;
        else
        {
            if (p) p--;
            while (i + p <= n && sa[rk[i] - 1] + p <= n
                && s[i + p] == s[sa[rk[i] - 1] + p]) p++;
        }
        h[rk[i]] = p;
    }
    /*求h數(shù)組 h[k]=LCP(suffix[sa[k]],suffix[sa[k+1]]) */
    /*int o, b;
    for (int i = 0; i < n; i++) {
        o = rk[i];//在sa數(shù)組中的位置
        if (o == n) continue;
        b = sa[o + 1];//b為要和i匹配的后綴的位置
        while (i+h[o]<=n&&b+h[o]<=n
            &&s[i + h[o]] == s[b + h[o]]) ++h[o];
        h[rk[i + 1]] = max(0, h[o] - 1);
    }*/
    /*
    for (int i = 1; i <= n; i++) {
        cout << rk[i] << " ";
    }
    cout << endl;
    for (int i = 1; i <= n; i++) {
        cout << h[i] << " ";
    }
    cout << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = sa[i]; j <= n; j++) {
            cout << a[j];
        }
        cout << endl;
    }
    cout << endl;*/
}
/* dp[i][j]表示[i,i+2^j-1]的區(qū)間最小值              */
/* dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1])   */
void rmq_init() {
    int len = n;
    for (int i = 1; i <= len; i++)
        dp[i][0] = h[i];
    for (int j = 1; (1 << j) <= len; j++) {
        for (int i = 1; i + (1 << j) - 1 <= len; i++) {
            dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
        }
    }
}
/* 查詢h[l...r]上的區(qū)間最小值    */      
int rmq(int l, int r) {
    int k = 0;
    while ((1 << (k + 1)) <= r - l + 1)
        k++;
    int ans = min(dp[l][k], dp[r - (1 << k) + 1][k]);
    return ans;
}
void solve() {
    rmq_init();
    int ans = -1;
    for (int i = 1; i <= n - K+1; i++) {
        ans = max(ans, rmq(i+1, i + K - 1));//h[i+1]...h[i+K-1]
    }
    cout << ans << endl;
}
int main() {
    cin >> n >> K;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    build_sa(a);
    solve();
    return 0;
}