星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

题解 P4022 【[CTSC2012]熟悉的文章】

posted on 2018-06-12 21:07:37 | under 题解 |

$60pts:$
有一个常见的套路是:看见序列分段想 $\Theta(n^2)DP+$ 优化。
这题目要的是 $L$ 的最大值,那么不影响我们 $DP$ 的结果,可以直接二分答案。
这个分段的 $DP$ 也是很显然,设 $dp_i$ 表示以i作为当前段结尾:
$$dp_i=\max(dp_j+i-(j+1)+1,dp_{i-1}),j\in [i-maxlen_i,i-l]$$ 其中, $maxlen_i$ 表示以 $i$ 为结尾的字符串出现在模板串中的最长长度,这个可以用 $SAM$ 一开始跑出来; $l$ 表示当前二分的答案。
这样我们得到了(上界复杂度) $O(n^2\log n)$ 的算法。

$100pts:$
决策单调性很显然,因为 $i-maxlen_i$ 一定是单调递增的。
发现决策单调性之后,将 $dp$ 方程改成 $dp_j-j+i$ , $i$ 显然单调递增,那么就可以维护前面这个 $dp_j-j$ 的单调递减队列了。复杂度 $O(n\log n)$ 。
$P.S.$ 其实没有必要用广义 $SAM$ 的,只要隔一个字符插就可以了,虽然空间貌似有那么一点儿......大?

#include<cstdio>
#include<cstring>
#include<deque>
#define neko 2000010
#define chkmax(a,b) ((a)>(b)?(a):(b))
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~(i)))
typedef int arr[neko];
arr link,len,dp,maxlen,q;
int n,m,nex[neko][3];
namespace SAM
{
    int slen,cnt,cur,last;
    void find(char *s)
    {
        int p=0,now=0,x;
        slen=strlen(s+1);
        f(i,1,slen)
        {
            x=s[i]-'0';
            if(nex[p][x])++now,p=nex[p][x];
            else
            {
                for(;p!=-1&&(!nex[p][x]);p=link[p]);
                if(p==-1)p=0,now=0;
                else now=len[p]+1,p=nex[p][x];
            }maxlen[i]=now;
        }
    }//this is right
    void extend(char *s)
    {
        int p,q,clone,x;
        link[0]=-1,slen=strlen(s+1);s[++slen]='2';
        f(i,1,slen)
        {
            cur=++cnt,len[cur]=len[last]+1;
            x=s[i]-'0';
            for(p=last;p!=-1&&(!nex[p][x]);p=link[p])nex[p][x]=cur;
            if(p==-1)link[cur]=0;
            else
            {
                q=nex[p][x];
                if(len[p]+1==len[q])link[cur]=q;
                else
                {
                    clone=++cnt;
                    len[clone]=len[p]+1;
                    link[clone]=link[q];
                    f(j,0,1)nex[clone][j]=nex[q][j];
                    for(;p!=-1&&(nex[p][x]==q);p=link[p])nex[p][x]=clone;
                    link[q]=link[cur]=clone;
                }
            }last=cur;
        }
    }
}
bool check(int l)
{
    int slen=SAM::slen,j,H=0,T=-1;
    //easily(?) to prove that it has a monotonicity of decision making
    f(i,0,l-1)dp[i]=0;
    f(i,l,slen)
    {
        dp[i]=dp[i-1];
        while(H<=T&&(dp[i-l]-(i-l))>(dp[q[T]]-q[T]))--T;
        q[++T]=i-l;
        while(H<=T&&q[H]<(i-maxlen[i]))++H;
        if(H<=T)dp[i]=chkmax(dp[i],dp[q[H]]-q[H]+i);//i-(j+1)+1
        //f(j,i-maxlen[i],i-l)if(dp[j]+(i-j)>dp[i])dp[i]=dp[j]+(i-j);//i-(maxlen[i]+1)+1
    }//f(i,1,slen)printf("%d ",dp[i]);puts("");
    return dp[slen]*10>=slen*9;
}
char s[neko];
#define mid ((l+r)>>1)
int main()
{
    using namespace SAM;
    int l,r;
    scanf("%d%d",&n,&m);
    f(i,1,m)scanf("%s",s+1),extend(s);
    f(i,1,n)
    {
        scanf("%s",s+1);
        l=1,r=strlen(s+1);
        find(s);
        while(l<=r)
        {
            //printf("%d %d %d\n",l,r,mid);
            if(check(mid))l=mid+1;
            else r=mid-1;
        }printf("%d\n",mid);
    }return 0;
}