分析

首先，可以发现，区间是可以合并滴。把区间按左端点排序，对于两个区间[l1,r1]、[l2,r2]，当l1<=l2 and r1>=l2，那么，将它们合成一个新的区间[l1,r2]。当一个位置不属于任何一个区间时，它自己独立成为一个区间。

接着dp，保证区间是从小到大的。

设f[i][j]表示在从S第i个区间，和子串T[j~|T|]的最长公共子串。

转移，

定义g[i]表示S第i个区间的长度

枚举子串T[j~j+g[i]-1]每一个位置，当枚举到k时，T[j~k]中T[k]的个数大于S第i个区间中T[k]的个数，那么就break，f[i][j]=k-j+1。如果f[i][j]等于g[i],那么，f[i][j]=f[i][j]+f[i+1][j+g[i]]。

但是，最长公共子串的串首并不一定是区间的串首，所以从i-1开始，往前搜，方法同上，设搜到的长度是num，ans就是max（num+f[i][j]）。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           const int maxlongint=2147483647;using namespace std;int lens,lent,f[4110][4100],g[5000],sum[2100][30],st[2100],b[100002][3],n,m,tot,ans,sm[30];char s[4100],t[4100];void q(int l,int r){ int i=l,j=r,mid=b[(l+r)/2][1],e; while(i
           
            mid) j--; if(i<=j) { e=b[i][1]; b[i][1]=b[j][1]; b[j][1]=e; e=b[i][2]; b[i][2]=b[j][2]; b[j][2]=e; i++; j--; } } if(i
            
             =1;i--) { for(int j=lent-1;j>=0;j--) { int bz=true,g1=0; memset(sm,0,sizeof(sm)); for(int k=j;k-j+1<=g[i];k++) { if(t[k]==t[-1]) { } else if(k<=lent-1 && ++sm[t[k]-96]<=sum[i][t[k]-96]) { f[i][j]++; } else { bz=false; break; } } if(bz) { f[i][j]+=f[i+1][j+g[i]]; } int num=0; memset(sm,0,sizeof(sm)); for(int k=j-1;k+g[i-1]-1>=j;k--) { if(++sm[t[k]-96]<=sum[i-1][t[k]-96]) { num++; } else { bz=false; break; } } if(f[i][j]+num>ans) { ans=f[i][j]+num; } } } printf("%d",ans);}