Description：

给两个串，求他们长度超过 $k$ 的相同公共子串对数。

$1\leqslant n\leqslant 10^5$

Solution：

先把两个字符串拼在一起求后缀数组，然后考虑怎么统计答案，利用单调栈可以维护他之前的所有后缀和他的 $lcp$ ，首先一对 $lcp=l(l\geqslant k)$ 的来自两个子串的后缀对答案的贡献是 $l-k+1$ ，那么我们就可以在栈中分别维护属于第一个串的 $h$ 的和和属于第二个串的 $h$ 的和，注意这里在统计的时候只统计 $lcp\geqslant k$ 的对数，然后就可以更新答案了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int k,l1,l2,n;

#define MAXN 320010

char a[MAXN],b[MAXN];

char s[MAXN];

int sa[MAXN],rnk[MAXN],c1[MAXN],c2[MAXN],height[MAXN];

int c[MAXN];

void make_SA(int n,int m)

{

	int p = 0;

	int *x = c1,*y = c2;

	for(int i = 1;i <= m;++i)c[i] = 0;

	for(int i = 1;i <= n;++i)++c[x[i] = s[i]];

	for(int i = 1;i <= m;++i)c[i] += c[i - 1];

	for(int i = n;i >= 1;--i)sa[c[x[i]]--] = i;

	for(int k = 1;k <= n;k = k << 1)

	{

		p = 0;

		for(int i = n - k + 1;i <= n;++i)y[++p] = i;

		for(int i = 1;i <= n;++i)if(sa[i] > k)y[++p] = sa[i] - k;

		for(int i = 1;i <= m;++i)c[i] = 0;

		for(int i = 1;i <= n;++i)++c[x[y[i]]];

		for(int i = 1;i <= m;++i)c[i] += c[i - 1];

		for(int i = n;i >= 1;--i)sa[c[x[y[i]]]--] = y[i];

		p = 1;

		swap(x,y);

		x[sa[1]] = 1;

		for(int i = 2;i <= n;++i)

		{

			x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p : ++p);

		}

		if(p >= n)break;

		m = p;

	}

	for(int i = 1;i <= n;++i)rnk[sa[i]] = i;

	int k = 0;

	for(int i = 1;i <= n;++i)

	{

		if(rnk[i] == 1)continue;

		if(k)--k;

		int j = sa[rnk[i] - 1];

		while(i + k <= n && j + k <= n && s[i + k] == s[j + k])++k;

		height[rnk[i]] = k;

	}

	return;

}

struct seg

{

	int l,r,h,cnt[2];

	seg(int l_,int r_,int h_,int cnt0,int cnt1){l = l_;r = r_;h = h_;cnt[0] = cnt0;cnt[1] = cnt1;}

	seg(){}

};

seg stack[MAXN];

int top = 0;

int ct[2];

long long sum[2];

int main()

{

	while(scanf("%d",&k) && k != 0)

	{

		scanf("%s%s",a + 1,b + 1);

		l1 = strlen(a + 1);

		l2 = strlen(b + 1);

		n = 0;

		long long ans = 0;

		for(int i = 1;i <= l1;++i)s[++n] = a[i];

		s[++n] = '#';

		for(int i = 1;i <= l2;++i)s[++n] = b[i];

		make_SA(n,256);

		for(int i = 1;i < n;++i)height[i] = height[i + 1];

		top = 0;

		sum[0] = sum[1] = ct[0] = ct[1] = 0;

		for(int i = 1;i <= n;++i)

		{

			ans += sum[(sa[i] > l1 + 1) ^ 1];

			ans -= ct[(sa[i] > l1 + 1) ^ 1] * (k - 1);

			int cnt[2] = {0,0};

			int l = i;

			while(top > 0 && stack[top].h >= height[i])

			{

				if(stack[top].h >= k)

				{

					ct[0] -= stack[top].cnt[0];

					ct[1] -= stack[top].cnt[1];

					sum[0] -= stack[top].cnt[0] * stack[top].h;

					sum[1] -= stack[top].cnt[1] * stack[top].h;

				}

				cnt[0] += stack[top].cnt[0];

				cnt[1] += stack[top].cnt[1];

				l = stack[top].l;

				--top;

			}

			cnt[(sa[i] > l1 + 1)] += 1;

			stack[++top] = (seg){l,i,height[i],cnt[0],cnt[1]};

			if(stack[top].h >= k)

			{

				ct[0] += stack[top].cnt[0];

				ct[1] += stack[top].cnt[1];

				sum[0] += stack[top].cnt[0] * stack[top].h;

				sum[1] += stack[top].cnt[1] * stack[top].h;

			}

		}

		cout << ans << endl;

	}

	return 0;

}