提供一个简单的后缀数组做法。

考虑贪心地每次匹配两个 lcp 最长的子串。

求出 height 数组，和P2178 [NOI2015] 品酒大会一样从大到小排序，用并查集维护即可。

只需要记录当前集合还未匹配的 $a$ 串子串和 $b$ 串子串数量。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+3;
char s[N];
int sa[N],u[N],v[N],h[N],t[N],f[N],id[N],p[N],q[N];
long long ans;
int gf(int x){return f[x]==x?x:f[x]=gf(f[x]);}
void mg(int x,int y,int w){
	p[y]+=p[x],q[y]+=q[x],f[x]=y;
	if(p[y]<q[y])return ans+=w*1ll*p[y],q[y]-=p[y],p[y]=0,void();
	ans+=w*1ll*q[y],p[y]-=q[y],q[y]=0;
}//合并两个集合，pq分别表示还未匹配的a串子串和b串子串数量
int main(){
	int*rk=u,*b=v,n,n2,o,m=131,i,j,k=0,x,y;
	scanf("%d%d",&n2,&o),scanf("%s",s+1),s[n2+1]='z'+1,scanf("%s",s+n2+2),n=n2*2+1;
	for(i=1;i<=n;++i)++t[s[i]];
	for(i=1;i<=m;++i)t[i]+=t[i-1];
	for(i=n;i;--i)sa[t[rk[i]=s[i]]--]=i;
	for(i=1;k<n;i*=2,m=k){
		for(j=n-i+1,k=0,memset(t,0,m*4+4);j<=n;++j)b[++k]=j;
		for(j=1;j<=n;++j)if(++t[rk[j]],sa[j]>i)b[++k]=sa[j]-i;
		for(j=1;j<=m;++j)t[j]+=t[j-1];
		for(j=n;j;--j)sa[t[rk[b[j]]]--]=b[j];
		for(j=1,swap(rk,b),k=y=0;j<=n;++j,y=x)x=sa[j],rk[x]=b[x]==b[y]&&b[x+i]==b[y+i]?k:++k;
	}
	for(i=1,k=0;i<=n;h[rk[i++]]=k)if(rk[i]>1)for(j=sa[rk[i]-1],k=max(0,k-1);s[i+k]==s[j+k];++k);//以上为后缀数组板子
	for(i=1;i<=n;++i)if(f[i]=id[i]=i,i<=n2-o+1)p[i]=1;else if(i>n2+1&&i<=n2*2-o+2)q[i]=1;
	sort(id+2,id+n,[](int x,int y){return h[x]>h[y];});
	for(i=2;i<n;++i)mg(gf(sa[id[i]]),gf(sa[id[i]-1]),max(0,o-h[id[i]]));
	cout<<ans;
	return 0;
}

#include <bits/stdc++.h>
using std::cin;
using std::cout;

typedef long long ll;
const int N = 154000;

namespace SAM {
	const int N = 600054;

	int p, np, cnt = 1;
	int pa[N], d[N][26], val[N];
	int child[N][26], deg[N];

	#define q d[p][x]
	#define try_split(v) { \
		if (val[p] + 1 == val[q]) v = q; \
		else { \
			int nq = ++cnt; \
			val[nq] = val[p] + 1, memcpy(d[nq], d[q], 104); \
			pa[nq] = pa[q], v = pa[q] = nq; \
			for (int Q = q; p && q == Q; q = nq, p = pa[p]); \
		} \
	}

	int extend(int x) {
		if (p = np, q) try_split(np)
		else {
			for (val[np = ++cnt] = val[p] + 1; p && !q; q = np, p = pa[p]);
			if (p) try_split(pa[np]) else pa[np] = 1;
		}
		return np;
	}
	#undef q

	inline void build() {for (int i = 2; i <= cnt; ++i) child[pa[i]][deg[pa[i]]++] = i;}
}

int n, K;
int w[SAM::N];
char s[N], t[N];

inline int min(const int x, const int y) {return x < y ? x : y;}

void dfs(int x) {
	int i, y;
	for (i = 0; i < SAM::deg[x]; ++i) dfs(y = SAM::child[x][i]), w[x] += w[y];
}

int main() {
	int i, x; ll ans = 0;
	std::ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> n >> K >> s >> t, std::reverse(s, s + n), std::reverse(t, t + n);
	for (SAM::np = 1, i = 0; i < n; ++i) SAM::extend(s[i] - 97);
	for (SAM::np = 1, i = 0; i < n; ++i) SAM::extend(t[i] - 97);
	SAM::build();
	for (x = 1, i = 0; i < K - 1; ++i) x = SAM::d[x][s[i] - 97];
	for (; i < n; ++i, ++w[x])
		for (x = SAM::d[x][s[i] - 97]; SAM::val[SAM::pa[x]] >= K; x = SAM::pa[x]);
	for (x = 1, i = 0; i < K - 1; ++i) x = SAM::d[x][t[i] - 97];
	for (; i < n; ++i, --w[x])
		for (x = SAM::d[x][t[i] - 97]; SAM::val[SAM::pa[x]] >= K; x = SAM::pa[x]);
	dfs(1);
	for (i = 2; i <= SAM::cnt; ++i) if (w[i] > 0)
		x = min(SAM::val[i], K) - SAM::val[SAM::pa[i]],
		assert(x > 0), ans += (ll)x * w[i];
	cout << ans << '\n';
	return 0;
}