P4022 [CTSC2012]熟悉的文章

这真是个神dp
我肯定想不出来，太牛逼了

题解

假设我们知道了len[i]为i之前的最长匹配熟悉子串
我们可以二分答案，得到一个L
那么就可以得到 dp[i]表示匹配到i的最长熟悉长度
$$dp[i]=max(dp[j]+i?j)(i?len[i]<=j<=i?L)$$
把i提出
$$dp[i]=max(dp[j]?j)+i(i?len[i]<=j<=i?L)$$
维护一个dp[j]-j的单调队列就可以了
而i-len[i]是不减的，就没问题了
在判断是否>=0.9Len就可以了
那么怎么得到len[i]呢，建一个后缀自动机
跑一遍就出来了。。

#include<cstdio>
#include<iostream>
#include<cstring>
const int M=1100000;
#define mid (l+r>>1)
using namespace std;char s[M];
int n,m,last,tot=1,dis[M],ch[M][2],dp[M],f[M],len[M],Len,q[M];
void insert(int x){int now=last;last=++tot;dis[last]=dis[now]+1;while(!ch[now][x]&&now) ch[now][x]=last,now=f[now];if(!now) f[last]=1;else {int p=ch[now][x];if(dis[now]+1==dis[p]) f[last]=p;else{int np=++tot;memcpy(ch[np],ch[p],sizeof ch[p]);f[np]=f[p];f[p]=f[last]=np;dis[np]=dis[now]+1;while(now&&ch[now][x]==p) ch[now][x]=np,now=f[now];}}
}
void MAKE_len(){//printf("1");int now=1,sum=0;for(int i=1;i<=Len;i++){if(ch[now][s[i]-'0']) now=ch[now][s[i]-'0'],sum++;else {while(!ch[now][s[i]-'0']&&now) now=f[now];if(!now) now=1,sum=0;else sum=dis[now]+1,now=ch[now][s[i]-'0'];}len[i]=sum;}//for(int i=1;i<=Len;i++) printf("%d ",len[i]);
}
int check(int L){for(int i=1,head=1,tail=0;i<=Len;i++){dp[i]=dp[i-1];if(i-L<0) continue;while(head<=tail&&dp[q[tail]]-q[tail]<dp[i-L]-i+L) tail--;q[++tail]=i-L;while(head<=tail&&q[head]<i-len[i]) head++;if(head<=tail) dp[i]=max(dp[i],dp[q[head]]+i-q[head]);//printf("dp:%d ",dp[i]);}//puts("");return dp[Len]*10>=Len*9;
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) {last=1;scanf("%s",s+1);Len=strlen(s+1);for(int i=1;i<=Len;i++) insert(s[i]-'0'); }for(int i=1;i<=n;i++){scanf("%s",s+1);Len=strlen(s+1);MAKE_len();int l=0,r=Len;while(l<=r){if(check(mid)) l=mid+1;else r=mid-1;}printf("%d\n",l-1);}}