【CTSC2012】bzoj2806 Cheat

建出模板串的广义后缀自动机，就可以方便地对询问串计算出$f_i$表示以$i$结尾的子串最多能匹配多长。二分答案$x$，设前$i$位最多匹配$dp_i$位，我们可以列出方程

$$dp_i=\max\{dp_{i-1},dp_j+i-j(x\le i-j \le f_i)\}$$
后面那个限制条件变形为 $i-f_i\le j\le i-x$。 $i-x$显然单调，而容易发现 $f_{i+1}\le f_i+1$，因此 $i-f_i$也单调。于是我们可以用单调队列优化dp，判断就很简单了。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=3500000;
const double eps=1e-10;
char s[maxn];
int trie[maxn][2],trans[maxn][2],fail[maxn],val[maxn],
id[maxn],que[maxn],dp[maxn],f[maxn],
q,n,m,num,tot=1;
int add(int u,int x)
{int nu=++tot,v,nv;val[nu]=val[u]+1;while (u&&!trans[u][x]){trans[u][x]=nu;u=fail[u];}if (!u) fail[nu]=1;else{v=trans[u][x];if (val[v]==val[u]+1) fail[nu]=v;else{val[nv=++tot]=val[u]+1;fail[nv]=fail[v];fail[v]=fail[nu]=nv;trans[nv][0]=trans[v][0];trans[nv][1]=trans[v][1];while (u&&trans[u][x]==v){trans[u][x]=nv;u=fail[u];}}}return nu;
}
int main()
{int u,hd,tl,now,x,l,r,mid;scanf("%d%d",&q,&m);while (m--){scanf("%s",s+1);n=strlen(s+1);u=0;for (int i=1;i<=n;i++){if (!trie[u][s[i]-'0']) trie[u][s[i]-'0']=++num;u=trie[u][s[i]-'0'];}}id[0]=1;que[hd=tl=1]=0;while (hd<=tl){u=que[hd++];if (trie[u][0]){id[trie[u][0]]=add(id[u],0);que[++tl]=trie[u][0];}if (trie[u][1]){id[trie[u][1]]=add(id[u],1);que[++tl]=trie[u][1];}}while (q--){scanf("%s",s+1);n=strlen(s+1);u=1;now=0;for (int i=1;i<=n;i++){x=s[i]-'0';if (!trans[u][x]){while (u&&!trans[u][x]) u=fail[u];now=val[u];}if (!u){u=1;f[i]=now=0;}else{u=trans[u][x];f[i]=++now;}}l=0;r=n;while (l<r){mid=(l+r+1)/2;hd=1,tl=0;for (int i=1;i<=n;i++){if (i-mid>=0){while (hd<=tl&&dp[que[tl]]-que[tl]<=dp[i-mid]-i+mid) tl--;que[++tl]=i-mid;}while (hd<=tl&&que[hd]<i-f[i]) hd++;dp[i]=dp[i-1];if (hd<=tl) dp[i]=max(dp[i],dp[que[hd]]+i-que[hd]);}if (dp[n]+eps>=n*0.9) l=mid;else r=mid-1;}printf("%d\n",l);}
}