如果不存在模糊点，那么答案就是两个串的最长公共子串。

如果模糊点是某个串的开头或者结尾，那么可以暴力枚举另一个串中的某个前后缀更新答案。

否则，假设模糊点在第一个串里是$i$，在第二个串里是$j$，那么此时对答案的贡献为$lcp(i+1,j+1)+lcs(i-1,j-1)+1$。

将两个串用特殊字符拼接，求出正串的后缀数组以及反串的后缀数组，那么$lcp(i+1,j+1)+lcs(i-1,j-1)+1$等价于两个height数组的区间最小值的和。

考虑从大到小枚举第一个数，每次把所有大于等于它的部分全部合并，那么在另一个数组里显然只有相邻的后缀有用。

所以对于每个集合建立两棵平衡树，维护两个串在反串里的rank。

在启发式合并的时候，只需要在另一个串对应的平衡树里找到前驱后继然后更新答案即可。

时间复杂度$O(n\log^2n)$。

 

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N=400010,M=200005;char sa[N],sb[N],s[N];int na,nb,n,i,j,Log[N],ans;struct DS{  char s[N];  int rk[N],sa[N],height[N],tmp[N],cnt[N],f[18][M];  void suffixarray(int n,int m){    int i,j,k;n++;    for(i=0;i
         
          =n-1)break;    }    for(j=rk[height[i=k=0]=0];i
          
           y)swap(x,y); return ask(x+1,y); }}A,B;int q[M],f[M],ca[M],cb[M],size[M],g[M],v[M<<1],nxt[M<<1],ed,lcp;set
           
            TA[M],TB[M];inline bool cmp(int x,int y){return A.height[x]>A.height[y];}inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}void dfs(int x,int y,int z){ f[x]=z; if(A.sa[x]
            
             =0){ j=B.rk[n-1-j]; TA[z].insert(j); set
             
              ::iterator k=TB[z].lower_bound(j); if(k!=TB[z].end())ans=max(ans,lcp+B.lcp(j,*k)); if(k!=TB[z].begin())k--,ans=max(ans,lcp+B.lcp(j,*k)); } } if(A.sa[x]>na){ int j=A.sa[x]-2; if(j>na){ j=B.rk[n-1-j]; TB[z].insert(j); set
              
               ::iterator k=TA[z].lower_bound(j); if(k!=TA[z].end())ans=max(ans,lcp+B.lcp(j,*k)); if(k!=TA[z].begin())k--,ans=max(ans,lcp+B.lcp(j,*k)); } } for(int i=g[x];i;i=nxt[i])if(v[i]!=y)dfs(v[i],x,z);}inline void merge(int x,int y){ x=f[x],y=f[y]; if(size[x]>size[y])swap(x,y); if(ca[x]&&cb[y]||cb[x]&&ca[y])ans=max(ans,lcp-1); ca[y]|=ca[x],cb[y]|=cb[x],size[y]+=size[x]; TA[x].clear(),TB[x].clear(); add(x,y),add(y,x); dfs(x,y,y);}int main(){ for(i=2;i
               
                >1]+1; scanf("%s%s",sa,sb); na=strlen(sa); nb=strlen(sb); if(na==1||nb==1)return puts("1"),0; for(i=0;i
                
                 =0)TA[i].insert(B.rk[n-1-j]); } if(A.sa[i]>na){ cb[i]=1; j=A.sa[i]-2; if(j>na)TB[i].insert(B.rk[n-1-j]); } } for(i=1;i
                 
                  na+1)ans=max(ans,lcp); } for(lcp=N,i=j+1;i<=n;i++){ lcp=min(lcp,A.height[i]); if(A.sa[i]>na+1)ans=max(ans,lcp); } j=A.rk[na+2]; for(lcp=N,i=j-1;i;i--){ lcp=min(lcp,A.height[i+1]); if(A.sa[i]&&A.sa[i]
                  
                   nb+1)ans=max(ans,lcp); } for(lcp=N,i=j+1;i<=n;i++){ lcp=min(lcp,B.height[i]); if(B.sa[i]>nb+1)ans=max(ans,lcp); } return printf("%d",ans+1),0;}