bzoj 2806: [Ctsc2012]Cheat 后缀自动机DP

2806: [Ctsc2012]Cheat

Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 583 Solved: 330
[Submit][Status][Discuss]

Description

Input

第一行两个整数N，M表示待检查的作文数量，和小强的标准作文库
的行数
接下来M行的01串，表示标准作文库
接下来N行的01串，表示N篇作文

Output

N行，每行一个整数，表示这篇作文的Lo 值。

Sample Input

1 2
10110
000001110
1011001100

Sample Output

HINT

输入文件不超过1100000字节

注意：题目有改动,可识别的长度不小于90%即可，而不是大于90%

　　先将作文库建后缀自动机，多篇文章可以通过在中间加入分隔符来完成。对于每组询问，预处理出每一个位置向前最多匹配多长g[]。

　　二分答案len，dp[]表示匹配到当前位置的最多匹配数，对于i位置，dp[i]由一段通过len，与g确定出的区间[l,r]转移，本来用了一个线段树维护，但是由于时间复杂度O(n*log^2n)，TLE了，观察发现[l,r]是单调的，故可直接用单调队列。

　　网上一半题解过不了数据：1 1 1 1

　　另外，对于0.9的问题确实说明了以后能用int就不要用double，实在不行要加eps。

　　省选前最后一题了，真觉得时间过得太快了。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define MAXN 4100000

#define MAXT MAXN*4

#define INF 0x3f3f3f3f

#define lch (now<<1)

#define rch (now<<1^1)

#define smid ((l+r)>>1)

char buf[MAXN];

char *bufnow(buf);

int len[MAXN];

char *str[MAXN];

char buf2[MAXN];

char *bufnow2(buf2);

struct sam_node

{

        int nxt[];

        int pnt,len;

        void Print()

        {

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

                        printf("%d[%d] ",i,nxt[i]);

                printf("\n");

                printf("Pnt:%d\n",pnt);

        }

}sam[MAXN];

int tops=;

int last=;

void Add_item(int w)

{

        int p=last;

        int np=++tops;

        sam[np].len=sam[p].len+;

        while (p && !sam[p].nxt[w])

                sam[p].nxt[w]=np,p=sam[p].pnt;

        if (!p)

        {

                last=np;

                sam[np].pnt=;

        }else

        {

                int q=sam[p].nxt[w];

                if (sam[p].len+==sam[q].len)

                {

                        sam[np].pnt=q;

                }else

                {

                        int nq=++tops;

                        sam[nq]=sam[q];

                        sam[nq].len=sam[p].len+;

                        sam[nq].pnt=sam[q].pnt;

                        sam[q].pnt=nq;

                        sam[np].pnt=nq;

                        while (p && sam[p].nxt[w]==q)

                        {

                                sam[p].nxt[w]=nq;

                                p=sam[p].pnt;

                        }

                }

        }

        last=np;

}

int g[MAXN];

int dp[MAXN];

int seq[MAXN];

int main()

{

        freopen("input.txt","r",stdin);

        int n,m;

        int x,y;

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

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

        {

                scanf("%s\n",bufnow2);

                bufnow2+=strlen(bufnow2);

                *(bufnow2++)='';

        }

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

        {

                scanf("%s\n",bufnow);

                str[i]=bufnow;

                bufnow+=len[i]=strlen(bufnow);

                bufnow++;

        }

        for (char *i=buf2;i!=bufnow2;i++)

        {

                Add_item(*i-'');

        }

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

        {

        //        printf("SAM<%d>:\n",i);

        //        sam[i].Print();

        }

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

        {

                int now=;

                int clen=;

                for (int j=;j<len[i];j++)

                {

                        int w=str[i][j]-'';

                        if (sam[now].nxt[w])

                        {

                                now=sam[now].nxt[w];

                                clen++;

                        }else

                        {

                                while (now && !sam[now].nxt[w])

                                        now=sam[now].pnt;

                                if (!now)

                                {

                                        now=;

                                        clen=;

                                }else

                                {

                                        clen=sam[now].len+;

                                        now=sam[now].nxt[w];

                                }

                        }

                        g[j]=clen;

            //            printf("%d\n",clen);

                }

                for (int j=len[i];j>=;j--)

                        g[j]=g[j-];

                g[]=;

                int l=,r=len[i]+;

                int mid;

                int head,tail=;

                int ny;

                while (l+<r)

                {

                        mid=(l+r)>>;

                        int t;

                        for (int j=;j<=len[i];j++)

                                dp[j]=-INF;

                        dp[]=;

                        head=,tail=-;

                        ny=;

                        for (int j=;j<=len[i];j++)

                        {

                                x=j-g[j];

                                y=j-mid;

                                while (ny<=y)

                                {

                                        while (head<=tail && dp[seq[tail]]<=dp[ny])

                                                tail--;

                                        seq[++tail]=ny++;

                                }

                                while (head<=tail && seq[head]<x)

                                        head++;

                                dp[j]=dp[j-]+(j-);

                                if (head<=tail)

                                        dp[j]=max(dp[j],dp[seq[head]]+j);

                                dp[j]-=j;

                        }

                        t=dp[len[i]]+len[i];

                        if (t*>=len[i]*)

                                l=mid;

                        else

                                r=mid;

                }

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

        }

}

巴特西