mdzz

题解很简单:

钦定一对(i,j)可以不相等,贡献就是lcp(i+1,j+1)+lcs(i-1,j-1)

套路地

按照hei对lcp也就是height进行合并

最大化lcs

set启发式合并

 

错误点:

1.sa写错

2.a=fin(a),并查集也能写错

3.ST表(i+(1<<j)-1)<=n

**

#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define pb push_back#define solid const auto &#define enter cout<
      
       using namespace std;typedef long long ll;template 
       
        il void rd(T &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar())) (ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}template 
        
         il void prt(T a[],int st,int nd){    for(reg i=st;i<=nd;++i) cout<
         
          <<" ";cout<
          
           k) y[++num]=sa[i]-k; } for(reg i=1;i<=m;++i) buc[i]=0; for(reg i=1;i<=n;++i) ++buc[x[i]]; for(reg i=1;i<=m;++i) buc[i]+=buc[i-1]; for(reg i=n;i>=1;--i) sa[buc[x[y[i]]]--]=y[i],y[i]=0; swap(x,y); num=1; x[sa[1]]=1; for(reg i=2;i<=n;++i){ x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k])?num:++num; } if(num==n) break; m=num; } for(reg i=1;i<=n;++i) rk[sa[i]]=i; for(reg k=0,i=1;i<=n;++i){ if(k)--k; if(rk[i]==1) continue; int j=sa[rk[i]-1]; while(j+k<=n&&i+k<=n&&s[i+k]==s[j+k]) ++k; hei[rk[i]]=k; } for(reg i=1;i<=n;++i) f[i][0]=hei[i]; for(reg j=1;j<=17;++j){ for(reg i=1;(i+(1<
           
            <=n;++i){ f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]); } } //cout<<"string ";cout<
            
             <
             
              y) swap(x,y); ++x; int len=lg[y-x+1]; int ret=min(f[x][len],f[y-(1<
              
               n?n+(n+m)-x+1:n-x+1;}struct po{ int x; po(){} po(int xx){ x=xx; } bool friend operator <(po a,po b){ int ta=rev(a.x); int tb=rev(b.x); return str[1].rk[ta]
               
                str[0].hei[y];}set
                
                 s[N][2];int ans;int fin(int x){ return fa[x]==x?x:fa[x]=fin(fa[x]);}void merge(int a,int b,int l){ //cout<<" merge ----------"<
                 <<" "<<<" "<
                   
                    <
                    
                     >(lg[i-1]+1))?lg[i-1]+1:lg[i-1]; } for(reg i=2;i<=n;++i){ str[0].s[++str[0].n]=A[i]; //id[str[0].n]=1; } str[0].s[++str[0].n]='A'; for(reg i=2;i<=m;++i){ str[0].s[++str[0].n]=B[i]; //id[str[0].n]=2; } str[0].s[++str[0].n]='B'; reverse(A+1,A+n+1); reverse(B+1,B+m+1); for(reg i=2;i<=n;++i){ str[1].s[++str[1].n]=A[i]; //id[str[1].n]=1; } str[1].s[++str[1].n]='A'; for(reg i=2;i<=m;++i){ str[1].s[++str[1].n]=B[i]; //id[str[1].n]=2; } str[1].s[++str[1].n]='B'; str[0].build(); str[1].build(); for(reg i=1;i<=str[0].n;++i){ fa[i]=i; id[i]=i; if(i<=n){ s[i][0].insert(po(i)); }else{ s[i][1].insert(po(i)); } } sort(id+1,id+str[0].n+1,cmp); for(reg i=1;i<=str[0].n;++i){ int x=id[i]; if(x==1) continue; merge(str[0].sa[x],str[0].sa[x-1],str[0].hei[x]); } printf("%d",ans); return 0;}}signed main(){ Miracle::main(); return 0;}