后缀数组模板

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 8, M = 1e6 + 8;
int n, a[N], K, ans, q[N];
int cnt[M], t1[N], t2[N], sa[N], ht[N], rk[N];
void build_sa(int m, int *s)
{
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= n; i++) m = max(m, s[i]), cnt[t1[i] = s[i]]++;
    for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for (int i = 1; i <= n; i++) sa[cnt[t1[i]]--] = i;
    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];  
        for (int i = n; i >= 1; i--) sa[cnt[t1[t2[i]]]--] = t2[i];

        for (int i = 1; i <= n; i++) swap(t1[i], t2[i]);
        p = 0; t1[sa[1]] = ++p;
        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;
    }

    for (int i = 1; i <= n; i++) rk[sa[i]] = i;
    for (int i = 1, h = 0; i <= n; i++)
    {
        if (rk[i] == 1) h = 0;
        else
        {
            if (h) h--;
            while (i + h <= n && sa[rk[i] - 1] + h <= n 
                && s[i + h] == s[sa[rk[i] - 1] + h]) h++;
        }
        ht[rk[i]] = h;
    }
}
void solve()
{
    int l = 1, r = 0;
    for (int i = 2; i <= n - K + 2; i++)
    {
        while (l > r || q[r] < i + K - 2)
        {
            int p = q[r] + 1;
            while (l <= r && ht[p] < ht[q[r]]) r--;
            q[++r] = p;
        }
        while (l <= r && q[l] < i) l++;
        ans = max(ans, ht[q[l]]);
    }
    printf("%d\n", ans);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    scanf("%d%d", &n, &K);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    build_sa(n, a);
    solve();
#ifndef ONLINE_JUDGE
    fclose(stdin); fclose(stdout);
#endif
    return 0;
}

来自dzj