题意：给你两个字符串和k，求不小于k的公共子串的个数。
计算A的某个后缀与B的某个后缀的最长公共前缀L，如果L大于等于k，就加上L-k+1。
我们先把B复制到A后面，并加一个分隔符。
我们考虑同一组大于等于k的height，对于每个B计算之前每个A对其的贡献，对于每个A计算之前每个B对其的贡献。但这样是N2的。所以，我们利用lcp的性质，i~j所有height的最小值，所以我们只要维护一个单调递增的栈即可。
代码：
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
int K,l,n,top;
ll sum,ans;
int wa[200100],wb[200100],ws[200100],wv[200100],sa[200100],rank[200100],r[200100],height[200100],f[200100],a[200100],b[200100];
char s[200100];
int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int *r,int *sa,int n,int m)
{
int i,j,p,*x=wa,*y=wb,*t;
for (i=0;i<m;i++) ws[i]=0;
for (i=0;i<n;i++) ws[x[i]=r[i]]++;
for (i=1;i<m;i++) ws[i]+=ws[i-1];
for (i=n-1;i>=0;i--) sa[--ws[x[i]]]=i;
for (j=1,p=1;p<n;j*=2,m=p)
{
p=0;
for (i=n-j;i<n;i++) y[p++]=i;
for (i=0;i<n;i++) if (sa[i]>=j) y[p++]=sa[i]-j;
for (i=0;i<n;i++) wv[i]=x[y[i]];
for (i=0;i<m;i++) ws[i]=0;
for (i=0;i<n;i++) ws[wv[i]]++;
for (i=1;i<m;i++) ws[i]+=ws[i-1];
for (i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i];
for (t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
}
}
void calheight(int *r,int *sa,int n)
{
int i,j,k=0;
for (i=1;i<=n;i++) rank[sa[i]]=i;
for (i=0;i<n;height[rank[i++]]=k)
for (k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}
int main()
{
while (1)
{
scanf("%d",&K);
if (!K) break;
scanf("%s",s);
l=strlen(s);
s[l]=1;;
scanf("%s",s+l+1);
n=strlen(s);
for (int i=0;i<n;i++) r[i]=s[i];
r[n]=0;
da(r,sa,n+1,200);
calheight(r,sa,n);
for (int i=2;i<=n;i++)
{
f[i]=(sa[i]<l);
height[i]-=K-1;
if (height[i]<0) height[i]=0;
}
height[n+1]=0;
a[0]=-1;ans=0;
for (int id=0;id<=1;id++)
{
sum=0,top=0;
for (int i=2;i<=n;i++)
{
if (f[i]!=id) ans+=sum;
a[++top]=height[i+1];
b[top]=(f[i]==id);
sum+=(ll)a[top]*b[top];
while (a[top-1]>=a[top])
{
sum-=(ll)(a[top-1]-a[top])*b[top-1];
a[top-1]=a[top];
b[top-1]+=b[top];
top--;
}
}
}
printf("%lld\n",ans);
}
}
