Tjoi2019 甲苯先生和大中锋的字符串 后缀自动机_差分

tjoi胆子好大，直接出了两道送分题......

都 9102 年了，还有省选出模板题QAQ......

Code:

#include <bits/stdc++.h>

#define setIO(s) freopen(s".in","r",stdin)

#define maxn 200010

using namespace std;

char str[maxn];

int n,C[maxn],rk[maxn],arr[maxn];

int dis[maxn],f[maxn],ch[maxn][30],last,tot,cnt[maxn];

void init() { last = tot = 1; }

void ins(int c){

    int np = ++tot, p = last;

    last = np, dis[np] = dis[p] + 1;

    while(p && !ch[p][c]) ch[p][c] = np, p = f[p];

    if(!p) f[np] = 1;

    else {

        int q = ch[p][c];

        if(dis[q] == dis[p] + 1) f[np] = q;

        else {

            int nq = ++tot;

            dis[nq] = dis[p] + 1;

            memcpy(ch[nq],ch[q],sizeof(ch[q]));

            f[np] = nq, f[nq] = f[q], f[q] = nq;

            while(p && ch[p][c] == q) ch[p][c] = nq, p = f[p];

        }

    }

    ++cnt[np];

}

void work()

{

    int k;

    init();

    scanf("%s%d",str + 1,&k), n = strlen(str + 1);

    for(int i = 1;i <= n; ++i)  ins(str[i] - 'a');

    for(int i = 1;i <= tot; ++i) ++C[dis[i]];

    for(int i = 1;i <= tot; ++i) C[i] += C[i - 1];

    for(int i = tot;i >= 1; --i) rk[C[dis[i]]--] = i;

    for(int i = tot;i >= 1; --i) {

        int u = rk[i];

        cnt[f[u]] += cnt[u];

        if(cnt[u] == k)

        {

            arr[dis[f[u]] + 1] += 1;

            arr[dis[u] + 1] -= 1;

        }

    }

    int ans = 0, p = 0;

    for(int i = 1;i <= tot; ++i) {

        arr[i] += arr[i - 1];

        if(arr[i] >= p && arr[i] != 0) ans = i, p = arr[i];

    }

    if(ans == 0)

        printf("-1\n");

    else

        printf("%d\n",ans);

    for(int i = 0;i <= tot; ++i)

    {

        for(int j = 0;j < 30; ++j) ch[i][j] = 0;

        cnt[i] = C[i] = arr[i] = 0;

    }

    last = tot = 0;

}

int main()

{

    // setIO("input");

    int T;

    scanf("%d",&T);

    while(T--) work();

    return 0;

}