BZOJ2806: [Ctsc2012]Cheat（广义后缀自动机，单调队列优化Dp）

Description

Input

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

Output

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

Sample Input

1 2
10110
000001110
1011001100

Sample Output

解题思路：

L0值具有单调性。

L0值为0时，一定有匹配，为1时只需要考虑字符集，为2时要考虑前后顺序，所以具有单调性，L0越小匹配长度越大,那么可以二分。

这道题要求不能覆盖，所以不能使用简单的Dp来解决，但也很明显，得知一个字符串某一位为结尾时最长匹配长度是很有用的QAQ

所以设f[i]为以文本串i结尾，最长可识别子串的长度，那么startpos就是i-f[i]，设Dp[i]表示匹配到i最长（可以不连续，但不小于L0）的最大匹配长度。

为了实现可不连续，Dp[i]初值为Dp[i-1]，所以Dp[i]的转移方程就是Dp[i]=max(Dp[i-1],max({Dp[j]+i-j|i-j>=L0}))

转移是O(n²)的过不了，可以将Dp[j]-j与i分离将Dp[j]-j用单调队列维护，就是O(n)的了^_^

代码：

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 struct sant{

     int tranc[];

     int len;

     int pre;

 }s[];

 int siz;

 int fin;

 int n,m;

 char tmp[];

 int maxl[];

 int dp[];

 int x[];

 void Insert(int c)

 {

     int nwp,nwq,lsp,lsq;

     nwp=++siz;

     s[nwp].len=s[fin].len+;

     for(lsp=fin;lsp&&!s[lsp].tranc[c];lsp=s[lsp].pre)

         s[lsp].tranc[c]=nwp;

     if(!lsp)

         s[nwp].pre=;

     else{

         lsq=s[lsp].tranc[c];

         if(s[lsq].len==s[lsp].len+)

             s[nwp].pre=lsq;

         else{

             nwq=++siz;

             s[nwq]=s[lsq];

             s[nwq].len=s[lsp].len+;

             s[nwp].pre=s[lsq].pre=nwq;

             while(s[lsp].tranc[c]==lsq)

             {

                 s[lsp].tranc[c]=nwq;

                 lsp=s[lsp].pre;

             }

         }

     }

     fin=nwp;

     return ;

 }

 bool can(int L0,int len)

 {

     dp[]=;

     int t=,h=;

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

     {

         dp[i]=dp[i-];

         if(i<L0)

             continue;

         while(t>=h&&dp[x[t]]-x[t]<=dp[i-L0]-i+L0)t--;

         x[++t]=i-L0;

         while(t>=h&&x[h]<i-maxl[i])h++;

         if(t>=h)

             dp[i]=std::max(dp[x[h]]+i-x[h],dp[i]);

     }

     return *dp[len]>=*len;

 }

 int main()

 {

     fin=++siz;

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

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

     {

         scanf("%s",tmp+);

         int len=strlen(tmp+);

         fin=;

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

             Insert(tmp[j]-'');

     }

     while(n--)

     {

         scanf("%s",tmp+);

         int len=strlen(tmp+);

         int root=;

         int mxl=;

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

         {

             int c=tmp[i]-'';

             if(s[root].tranc[c])

             {

                 root=s[root].tranc[c];

                 mxl++;

             }else{

                 while(!s[root].tranc[c])

                     root=s[root].pre;

                 if(!root)

                 {

                     root=;

                     mxl=;

                 }else{

                     mxl=s[root].len+;

                     root=s[root].tranc[c];

                 }

             }

             maxl[i]=mxl;

         }

         int ans=;

         int l=,r=len;

         while(l<=r)

         {

             int mid=(l+r)>>;

             if(can(mid,len))

             {

                 ans=mid;

                 l=mid+;

             }else

                 r=mid-;

         }

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

     }

     return ;

 }

巴特西