题意：
长度不小于 k 的公共子串的个数
分析：
基本思路是计算 A 的所有后缀和 B 的所有后缀之间的最长公共前缀的长度,把最长公共前缀长度不小于 k 的部分全部加起来。
先将两个字符串连起来,中间用一个没有出现过的字符隔开。按 height 值分组后,接下来的工作便是快速的统计每组中后缀之间的最长公共前缀之和。
扫描一遍,每遇到一个 B 的后缀就统计与前面的 A 的后缀能产生多少个长度不小于 k 的公共子串,
这里 A 的后缀需要用一个单调的栈来高效的维护。然后对 A 也这样做一次。
// File Name: 3415.cpp
// Author: Zlbing
// Created Time: 2013年09月07日 星期六 14时58分18秒 #include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
using namespace std;
#define CL(x,v); memset(x,v,sizeof(x));
#define INF 0x3f3f3f3f
#define LL long long
#define REP(i,r,n) for(int i=r;i<=n;i++)
#define RREP(i,n,r) for(int i=n;i>=r;i--)
//rank从0开始
//sa从1开始,因为最后一个字符(最小的)排在第0位
//height从2开始,因为表示的是sa[i-1]和sa[i]
const int MAXN=;
int rank[MAXN],sa[MAXN],X[MAXN],Y[MAXN],height[MAXN];
char s[MAXN];
int buc[MAXN];
void calheight(int n) {
int i , j , k = ;
for(i = ; i <= n ; i++) rank[sa[i]] = i;
for(i = ; i < n ; height[rank[i++]] = k)
for(k?k--: , j = sa[rank[i]-] ; s[i+k] == s[j+k] ; k++);
}
bool cmp(int *r,int a,int b,int l) {
return (r[a] == r[b] && r[a+l] == r[b+l]);
}
void suffix(int n,int m = ) {
int i , l , p , *x = X , *y = Y;
for(i = ; i < m ; i ++) buc[i] = ;
for(i = ; i < n ; i ++) buc[ x[i] = s[i] ] ++;
for(i = ; i < m ; i ++) buc[i] += buc[i-];
for(i = n - ; i >= ; i --) sa[ --buc[ x[i] ]] = i;
for(l = ,p = ; p < n ; m = p , l *= ) {
p = ;
for(i = n-l ; i < n ; i ++) y[p++] = i;
for(i = ; i < n ; i ++) if(sa[i] >= l) y[p++] = sa[i] - l;
for(i = ; i < m ; i ++) buc[i] = ;
for(i = ; i < n ; i ++) buc[ x[y[i]] ] ++;
for(i = ; i < m ; i ++) buc[i] += buc[i-];
for(i = n - ; i >= ; i --) sa[ --buc[ x[y[i]] ] ] = y[i];
for(swap(x,y) , x[sa[]] = , i = , p = ; i < n ; i ++)
x[ sa[i] ] = cmp(y,sa[i-],sa[i],l) ? p- : p++;
}
calheight(n-);//后缀数组关键是求出height,所以求sa的时候顺便把rank和height求出来
}
char ch[MAXN];
LL h[MAXN],w[MAXN];
//单调栈h中每个元素如h[j]代表一个区间，这个区间内每一个后缀与当前位置i的LCP都为h[j]
//w[j]表示与但前位置i的LCP为h[j]的个数 LL num[MAXN];
int top;
int main() {
int k;
while(~scanf("%d",&k))
{
if(!k)break;
scanf("%s",s);
scanf("%s",ch);
int len1=strlen(s);
int len2=strlen(ch);
s[len1]=;
for(int i=len1+;i<len1+len2+;i++)
s[i]=ch[i-len1-];
s[len1+len2+]=;
int n=len1+len2+;
suffix(n+);
initRMQ(n);
//当两个字串的公共子串大于k时，能产生geight[i]-k+1个大于k的子串
for(int i=;i<=n;i++)
height[i]=max(,height[i]-k+);
LL ans=;
top=;
num[]=;
//每遇到一个A的后缀，统计与前面B的后缀能产生多少个长度不小于 k 的公共子串
for(int i=;i<=n;i++)
{
if(height[i]==)
{
top=;
}
else
{
int cnt=;
for(;top&&h[top]>=height[i];top--)
{
cnt+=w[top];
}
h[++top]=height[i];
//当sa[i-1]为B的后缀时，加1
w[top]=cnt+(sa[i-]>len1);
num[top]=num[top-]+h[top]*w[top];
//sa[i]为A的后缀时，统计与前面B的后缀产生的公共子串
if(sa[i]<len1)
{
ans+=num[top];
}
}
}
top=;
num[]=;
for(int i=;i<=n;i++)
{
if(height[i]==)
{
top=;
}
else
{
int cnt=;
for(;top&&h[top]>=height[i];top--)
{
cnt+=w[top];
}
h[++top]=height[i];
w[top]=cnt+(sa[i-]<len1);
num[top]=num[top-]+h[top]*w[top];
if(sa[i]>len1)
{
ans+=num[top];
}
}
}
printf("%lld\n",ans);
} return ;
}