[BZOJ]2806: [Ctsc2012]Cheat-白红宇

[BZOJ]2806: [Ctsc2012]Cheat

阅读量：4544 次

发布时间：2019-06-08

本文共 2113 字，大约阅读时间需要 7 分钟。

题解:对于标准作文库建广义sam 预处理出查询串每个位置往前能匹配的最远位置二分答案L 然后设dp方程为

　　$$ dp[i]=max(dp[i-1],max(i-j+dp[j])\left ( i-L\geq j\geqslant i-num[i] \right )) $$

然后我们用单调队列来维护$ dp[i]-i $的最大值

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #define mp make_pair#define pb push_back#define pii pair
               
                #define link(x) for(edge *j=h[x];j;j=j->next)#define inc(i,l,r) for(int i=l;i<=r;i++)#define dec(i,r,l) for(int i=r;i>=l;i--)const int MAXN=2e6+10;const double eps=1e-8;#define ll long longusing namespace std;struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}ll read(){ ll x=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); return x*f;}int ch[MAXN][2],fa[MAXN],dis[MAXN];int cnt,cur,rt;void built(int x){ int last=cur;cur=++cnt;dis[cur]=dis[last]+1;int p=last; for(;p&&!ch[p][x];p=fa[p])ch[p][x]=cur; if(!p)fa[cur]=rt; else{ int q=ch[p][x]; if(dis[q]==dis[p]+1)fa[cur]=q; else{ int nt=++cnt;dis[nt]=dis[p]+1; memcpy(ch[nt],ch[q],sizeof(ch[q])); fa[nt]=fa[q];fa[q]=fa[cur]=nt; for(;ch[p][x]==q;p=fa[p])ch[p][x]=nt; } }}char s[MAXN];int num[MAXN];void ycl(char str[]){ int len=strlen(str);int len1=0;int temp=rt; for(int i=0;i
                
                 =totl&&dp[t]-t>=dp[st[totr]]-st[totr])totr--; st[++totr]=t; while(totl<=totr&&st[totl]
                 
                  =9*n);}int main(){ int n=read();int m=read(); int R=0; rt=cur=cnt=1; while(m--){ cur=1;scanf("%s",s); int len=strlen(s);R=max(R,len); for(int i=0;i
                  
                   >1; if(check(mid,len))ans=mid,l=mid+1; else r=mid-1; } printf("%d\n",ans); } return 0;}