问题可以转化为：$A$ 与 $B$ 所有前缀一一配对，LCP 之和最大是多少.
构建后缀树，然后对于点 $x$，若 LCP 为 $x$ 则贡献就是 $x$ 子树中 $A$ 点和 $B$ 点较小数量.
我们发现如果要求和最大，就贪心匹配.
由于后缀树中点 $x$ 的长度为 mx[x] ~ mx[pre[x]]，我们需要分类讨论 $LCP$ 的长度.
但是由于题中特殊条件，导致后缀树中的关键点（A,B 匹配到的点）都表示前缀，而根据 SAM 原理，这些前缀长度都等于 mx[x].
所以我们不用对 LCP 长度分类讨论，直接贪心即可.
code:
#include <bits/stdc++.h>
#define N 170000
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
ll ans;
char A[N],B[N];
int n,K,tot,last,edges;
int hd[N<<2],nex[N<<2],to[N<<2];
int ch[N<<2][26],pre[N<<2],mx[N<<2],cnt[2][N<<2],c0[N<<2],c1[N<<2];
void add(int u,int v) {
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;
}
void extend(int c) {
if(ch[last][c]) {
int p=last,q=ch[last][c];
if(mx[q]==mx[p]+1) last=q;
else {
int nq=++tot;
mx[nq]=mx[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
pre[nq]=pre[q],pre[q]=nq;
for(;p&&ch[p][c]==q;p=pre[p]) ch[p][c]=nq;
last=nq;
}
}
else {
int np=++tot,p=last;
mx[np]=mx[p]+1,last=np;
for(;p&&!ch[p][c];p=pre[p]) ch[p][c]=np;
if(!p) pre[np]=1;
else {
int q=ch[p][c];
if(mx[q]==mx[p]+1) pre[np]=q;
else {
int nq=++tot;
mx[nq]=mx[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[q]));
pre[nq]=pre[q],pre[np]=pre[q]=nq;
for(;p&&ch[p][c]==q;p=pre[p]) ch[p][c]=nq;
}
}
}
}
void dfs(int x) {
int y,z;
c0[x]=cnt[0][x];
c1[x]=cnt[1][x];
for(int i=hd[x];i;i=nex[i]) {
y=to[i],dfs(y);
c0[x]+=c0[y];
c1[x]+=c1[y];
}
int det=min(c0[x],c1[x]);
ans+=1ll*min(mx[x],K)*det;
c0[x]-=det;
c1[x]-=det;
}
int main() {
// setIO("input");
scanf("%d%d",&n,&K);
scanf("%s%s",A+1,B+1);
last=tot=1;
for(int i=n;i>=1;--i) {
extend(A[i]-'a');
if(i<=n-K+1) ++cnt[0][last];
}
last=1;
for(int i=n;i>=1;--i) {
extend(B[i]-'a');
if(i<=n-K+1) ++cnt[1][last];
}
for(int i=2;i<=tot;++i) {
add(pre[i],i);
}
dfs(1);
printf("%lld\n",1ll*K*(n-K+1)-ans);
return 0;
}
