bzoj2806

广义后缀自动机+二分+单调队列+dp

这道题其实就是一个简单dp，dp[i]表示匹配到i最长匹配多少，设val[i]表示当前位置和原串的最长公共长度，二分的长度是L，那么要求dp[i]=max(dp[i-1],dp[j]+i-j)要求L<=i-j<=val[i],那么也就是j>=i-val[i]，前面的l每次把不符合的L>i-j弹掉，由于val[i]每次最多增加1，所以i-val[i]是不增的，所以可以用单调队列维护。最先开始我还想怎么在自动机上dp，结果直接求出val就行了。

#include<bits/stdc++.h>

using namespace std;

const int N = 2.2e6 + ;

int n, m;

int q[N], dp[N], val[N];

char s[N];

namespace SAM

{

    struct node {

        int val, par;

        int ch[];

    } t[N];

    int last = , sz = , root = ;

    int nw(int _)

    {

        t[++sz].val = _;

        return sz;

    }

    void extend(int c)

    {

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

        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;

    }

} using namespace SAM;

bool check(int L, int n)

{

    int l = , r = , ans = ;

    for(int i = ; i <= n; ++i)

    {

        dp[i] = dp[i - ];

        if(i < L) continue;

        while(l <= r && dp[i - L] + L > dp[q[r]] + (i - q[r])) --r;

        q[++r] = i - L;

        while(l <= r && i - q[l] > val[i]) ++l;

        if(l > r || i - q[l] < L || i - q[l] > val[i]) continue;

        dp[i] = max(dp[i - ], dp[q[l]] + (i - q[l]));

    }

    return dp[n] *  >=  * n;

}

int main()

{

    scanf("%d%d", &n, &m);

    for(int i = ; i <= m; ++i)

    {

        last = root;

        scanf("%s", s + );

        int len = strlen(s + );

        for(int j = ; j <= len; ++j) extend(s[j] - '');

    }

    for(int i = ; i <= n; ++i)

    {

        scanf("%s", s + );

        int len = strlen(s + ), u = root, step = ;

        for(int j = ; j <= len; ++j)

        {

            if(t[u].ch[s[j] - '']) u = t[u].ch[s[j] - ''], ++step;

            else

            {

                while(u && !t[u].ch[s[j] - '']) u = t[u].par;

                if(!u) u = root, step = ;

                else

                {

                    step = t[u].val + ;

                    u = t[u].ch[s[j] - ''];

                }

            }

            val[j] = step;

        }

        int l = , r = len + , ans = ;

        while(r - l > )

        {

            int mid = (l + r) >> ;

            if(check(mid, len)) l = ans = mid;

            else r = mid;

        }

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

    }

    return ;

}

巴特西

bzoj2806

最新文章

热门文章