bzoj3998

后缀自动机+dp

想了挺长时间

后缀自动机的状态图是一个dag，从root走到一个点的路径数代表了这个状态包含的子串，我们先预处理出来每个节点向后走能够形成多少子串，注意这里不是直接在parent树上求和，我们先求出每个节点的right集合的大小，然后在状态图上统计儿子的路径数，因为向儿子走相当于添加一个字符，所以这里和Max没有关系，那么图上后继的Right和就是之后能够形成多少子串，然后就是查找第k大的过程了。这道题T=0的时候每个点的值都是1，因为相同的算一个，T=1就是Right集合的大小。

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + ;

int n, k, T;

int a[N], c[N], sum[N], val[N];

char s[N];

namespace SAM

{

    struct node {

        int val, par;

        int ch[];

    } t[N];

    int last = , root = , sz = ;

    int nw(int x)

    {

        t[++sz].val = x;

        return sz;

    }

    void extend(int c)

    {

        int p = last, np = nw(t[p].val + );

        val[np] = ;

        while(p && !t[p].ch[c]) t[p].ch[c] = np, p = t[p].par;

        if(!p) t[np].par = root;

        else

        {

            int q = t[p].ch[c];

            if(t[q].val == t[p].val + ) t[np].par = q;

            else

            {

                int nq = nw(t[p].val + );

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

                t[nq].par = t[q].par;

                t[q].par = t[np].par = nq;

                while(p && t[p].ch[c] == q) t[p].ch[c] = nq, p = t[p].par;

            }

        }

        last = np;

    }

    void RadixSort()

    {

        for(int i = ; i <= sz; ++i) ++c[t[i].val];

        for(int i = ; i <= sz; ++i) c[i] += c[i - ];

        for(int i = ; i <= sz; ++i) a[c[t[i].val]--] = i;

        for(int i = sz; i; --i)

        {

            int u = a[i];

            if(T == ) val[u] = ;

            else val[t[u].par] += val[u];

        }

        val[] = ;

        for(int i = sz; i; --i)

        {

            int u = a[i];

            sum[u] = val[u];

            for(int j = ; j < ; ++j) if(t[u].ch[j])

                sum[u] += sum[t[u].ch[j]];

        }

    }

    void print(int u)

    {

        if(k <= val[u]) return;

        k -= val[u];

        for(int i = ; i < ; ++i) if(t[u].ch[i])

        {

            if(k <= sum[t[u].ch[i]])

            {

                printf("%c", 'a' + i);

                print(t[u].ch[i]);

                return;

            }

            else k -= sum[t[u].ch[i]];

        }

    }

} using namespace SAM;

int main()

{

    scanf("%s%d%d", s + , &T, &k);

    n = strlen(s + );

    for(int i = ; i <= n; ++i) extend(s[i] - 'a');

    RadixSort();

    if(sum[] < k)

    {

        puts("-1");

        return ;

    }

    print(root);

    return ;

}

巴特西

bzoj3998

最新文章

热门文章