我们的目的就是找到一个最大的L0，使得该串的90%可以被分成若干长度>L0的字典串中的子串。

明显可以二分答案，对于二分的每个mid

我们考虑dp：f[i]表示前i个字符，最多能匹配上多少个字符。

发现转移端点是个不断前进的区间，单调队列优化就可以了。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #define N 2222222 7 #define eps 1e-8 8 using namespace std; 9 int last,tot,ch[N][2],par[N],mx[N];10 void add(int c){11     int p=last,np=++tot;mx[np]=mx[p]+1;12     for(;p&&!ch[p][c];p=par[p])ch[p][c]=np;13     if(!p)par[np]=1;14     else{15         int q=ch[p][c];16         if(mx[q]==mx[p]+1)par[np]=q;17         else{18             int nq=++tot;19             mx[nq]=mx[p]+1;20             par[nq]=par[q];21             memcpy(ch[nq],ch[q],sizeof ch[nq]);22             par[q]=par[np]=nq;23             for(;p&&ch[p][c]==q;p=par[p])ch[p][c]=nq;24         }25     }last=np;26 }27 char s[N];28 int n,m,len;29 int pp[N],f[N];30 void dfs(int v,int x,int l){31     int t=s[x+1]-'0';pp[x]=l;32     if(x==len)return ;33     if(ch[v][t])dfs(ch[v][t],x+1,l+1);34     else{35         while(!ch[v][t])v=par[v],l=min(l,mx[v]);36         dfs(ch[v][t],x+1,l+1);37     }38 }39 int head,tail,q[N];40 bool check(int x){41     head=1;tail=0;42     for(int i=1;i<=len;i++){43         f[i]=f[i-1];44         while(head<=tail&&q[head]
           
            =0){47 int t=i+1-x;48 while(head<=tail&&f[t]-t>=f[q[tail]]-q[tail])tail--;49 q[++tail]=t;50 }51 }52 double ans=f[len],tot=len;53 return ans>=(tot*0.9-eps);54 }55 int main(){56 mx[0]=-1;57 for(int i=0;i<2;i++)ch[0][i]=1;58 last=++tot;59 scanf("%d%d",&n,&m);60 while(m--){61 scanf("%s",s);len=strlen(s);62 last=1;for(int j=0;j
            
             >1;71 if(check(mid)){ans=mid;l=mid+1;}72 else r=mid-1;73 }74 printf("%d\n",ans);75 }76 return 0;77 }