很久以前写的，忘补结题报告了
两串相连中间用特殊的分隔符
然后求height，由于要求求公共子串大于等于k的个数，并且只要位置不同即可
因此不难想到在名次上对height分组，一组内的height保证>=k
下面就是在组内统计的问题了
然后还是不难发现，分别在AB串中的后缀i,j，他们能产生2*[LCP(i,j)-k+1]个公共子串
然后那个著名的性质LCP(i,j)=min(h[rank[i]+1]~h[rank[j]]) （令rank[i]<rank[j])
不难想到维护一个单调增的队列，遇到在B串就统计并维护，遇到在A串就维护
然后再反过来做一遍
具体维护单调队列见程序，否则感觉讲不清
type node=record
h,s:longint;
end;
var s,ss:ansistring;
h,sa,sum,y,x,rank:array[..] of longint;
n,m,i,j,loc,p,k,t,f:longint;
q:array[..] of node;
w,ans:int64; begin
readln(k);
while k<> do
begin
readln(s);
loc:=length(s)+;
readln(ss);
s:=s+' '+ss;
n:=length(s);
fillchar(sum,sizeof(sum),);
for i:= to n do
begin
y[i]:=ord(s[i]);
inc(sum[y[i]]);
end;
m:=;
for i:= to m do
inc(sum[i],sum[i-]);
for i:=n downto do
begin
sa[sum[y[i]]]:=i;
dec(sum[y[i]]);
end;
p:=;
rank[sa[]]:=;
for i:= to n do
begin
if y[sa[i]]<>y[sa[i-]] then inc(p);
rank[sa[i]]:=p;
end;
m:=p;
j:=;
while m<n do
begin
y:=rank;
fillchar(sum,sizeof(sum),);
p:=;
for i:=n-j+ to n do
begin
inc(p);
x[p]:=i;
end;
for i:= to n do
if sa[i]>j then
begin
inc(p);
x[p]:=sa[i]-j;
end;
for i:= to n do
begin
rank[i]:=y[x[i]];
inc(sum[rank[i]]);
end;
for i:= to m do
inc(sum[i],sum[i-]);
for i:=n downto do
begin
sa[sum[rank[i]]]:=x[i];
dec(sum[rank[i]]);
end;
p:=;
rank[sa[]]:=;
for i:= to n do
begin
if (y[sa[i]]<>y[sa[i-]]) or (y[sa[i]+j]<>y[sa[i-]+j]) then inc(p);
rank[sa[i]]:=p;
end;
j:=j shl ;
m:=p;
end;
h[]:=;
p:=;
for i:= to n do
begin
if rank[i]= then continue;
j:=sa[rank[i]-];
while s[i+p]=s[j+p] do inc(p);
h[rank[i]]:=p;
if p> then dec(p);
end; ans:=;
t:=;
f:=;
w:=;
if sa[]<loc then
begin
w:=w+h[]-k+;
q[t].h:=h[];
q[t].s:=;
inc(t);
end;
for i:= to n do
begin
if h[i]>=k then
begin
if sa[i]<loc then
begin
p:=;
w:=w+h[i+]-k+; //w维护组内到下一个在B中的后缀（LCP-k+）和
end
else if sa[i]>loc then
begin
ans:=ans+w;
if i=n then continue;
p:=; //这里注意，这是B串的后缀，不能和下一个B串后缀形成公共子串
end;
while (f<t) and (q[t-].h>=h[i+]) do //队中height比当前大直接退，因为它的height一定不是LCP
begin
w:=w-(q[t-].h-h[i+])*q[t-].s; //s域维护是队列中当前元素到队中前一个元素之间有多少比它height大
//这里显然之前height比当前大的元素和下一个B串后缀可能的LCP都应当是当前h[i+]
p:=p+q[t-].s;
dec(t);
end;
if p> then
begin
q[t].h:=h[i+];
q[t].s:=p;
inc(t);
end;
end
else begin
t:=;
w:=;
f:=;
if sa[i]<loc then
begin
q[t].h:=h[i+];
q[t].s:=;
w:=h[i+]-k+;
inc(t);
end;
end;
end; t:=;
f:=;
w:=;
if sa[]<loc then
begin
w:=w+h[]-k+;
q[t].h:=h[];
q[t].s:=;
inc(t);
end;
for i:= to n do
begin
if h[i]>=k then
begin
if sa[i]>loc then
begin
p:=;
w:=w+h[i+]-k+;
end
else if sa[i]<loc then
begin
ans:=ans+w;
if i=n then continue;
p:=;
end;
while (f<t) and (q[t-].h>=h[i+]) do
begin
w:=w-(q[t-].h-h[i+])*q[t-].s;
p:=p+q[t-].s;
dec(t);
end;
if p> then
begin
q[t].h:=h[i+];
q[t].s:=p;
inc(t);
end;
end
else begin
t:=;
w:=;
f:=;
if sa[i]>loc then
begin
q[t].h:=h[i+];
q[t].s:=;
w:=h[i+]-k+;
inc(t);
end;
end;
end;
writeln(ans);
readln(k);
end;
end.