后缀数组+单调栈。
与之前那题非常类似，我们依旧是采用height数组对答案进行计算。
非常强的操作，我们分别对b匹配a，对a匹配b。我们会发现他的height会越匹配越小，所以我们建立单调上升的栈来存下a串中相同的，然后一旦遇到小的就将他更新换掉，然后对答案统计计算，栈要再开一维计算之前有哪些高的被砍掉的。
By：大奕哥
1 #include<iostream> 2 #include<iostream> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<cstring> 7 using namespace std; 8 const int N=2e5+10; 9 int r[N],wa[N],wb[N],wv[N],wu[N],sa[N]; 10 int cmp(int *r,int a,int b,int l) 11 { 12 return r[a]==r[b]&&r[a+l]==r[b+l]; 13 } 14 void da(int *r,int *sa,int n,int m) 15 { 16 int i,j,p;int *x=wa,*y=wb; 17 for(i=0;i<m;++i)wu[i]=0; 18 for(i=0;i<n;++i)wu[x[i]=r[i]]++; 19 for(i=1;i<m;++i)wu[i]+=wu[i-1]; 20 for(i=n-1;i>=0;--i)sa[--wu[x[i]]]=i; 21 22 for(j=1,p=1;p<n;j<<=1,m=p) 23 { 24 for(p=0,i=n-j;i<n;++i)y[p++]=i; 25 for(i=0;i<n;++i)if(sa[i]>=j)y[p++]=sa[i]-j; 26 for(i=0;i<n;++i)wv[i]=x[y[i]]; 27 for(i=0;i<m;++i)wu[i]=0; 28 for(i=0;i<n;++i)wu[wv[i]]++; 29 for(i=1;i<m;++i)wu[i]+=wu[i-1]; 30 for(i=n-1;i>=0;--i)sa[--wu[wv[i]]]=y[i]; 31 for(swap(x,y),p=1,x[sa[0]]=0,i=1;i<n;++i) 32 x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; 33 } 34 return; 35 } 36 int rank[N],height[N],ans; 37 void calcHeight(int *rank,int *sa,int n) 38 { 39 int i,j,k=0; 40 for(i=1;i<=n;++i)rank[sa[i]]=i; 41 for(i=0;i<n;height[rank[i++]]=k) 42 for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];++k); 43 return ; 44 } 45 char aa[N],bb[N];int k,sta[N][2]; 46 int main() 47 { 48 while(~scanf("%d",&k)&&k) 49 { 50 scanf("%s",aa); 51 scanf("%s",bb); 52 int n1=strlen(aa); 53 int n2=strlen(bb); 54 int n=n1+n2+1; 55 for(int i=0;i<n;++i) 56 { 57 if(i<n1)r[i]=aa[i]; 58 else if(i==n1)r[i]='$'; 59 else r[i]=bb[i-n1-1]; 60 }r[n]=0; 61 da(r,sa,n+1,216); 62 calcHeight(rank,sa,n); 63 int top=0; 64 long long ans=0,tot=0; 65 for(int i=1;i<=n;++i) 66 { 67 if(height[i]<k)top=0,tot=0; 68 else 69 { 70 int cnt=0; 71 if(sa[i-1]<n1){ 72 cnt++;tot+=height[i]-k+1; 73 } 74 while(top&&height[i]<=sta[top][0]) 75 { 76 tot+=(height[i]-sta[top][0])*sta[top][1]; 77 cnt+=sta[top][1];top--; 78 } 79 sta[++top][0]=height[i];sta[top][1]=cnt; 80 if(sa[i]>n1){ 81 ans+=tot; 82 } 83 } 84 } 85 top=tot=0; 86 for(int i=1;i<=n;++i) 87 { 88 if(height[i]<k)top=0,tot=0; 89 else 90 { 91 int cnt=0; 92 if(sa[i-1]>n1){ 93 cnt++;tot+=height[i]-k+1; 94 } 95 while(top&&height[i]<=sta[top][0]) 96 { 97 tot+=(height[i]-sta[top][0])*sta[top][1]; 98 cnt+=sta[top][1];top--; 99 } 100 sta[++top][0]=height[i];sta[top][1]=cnt; 101 if(sa[i]<n1){ 102 ans+=tot; 103 } 104 } 105 } 106 printf("%lld\n",ans); 107 } 108 return 0; 109 }