思路是类似在 Trie 树上进行 dp，底下能匹配就匹配，剩下的合并上去。过程中加一个优化，每次用哈希求出当前所有字符串的 lcp，直接跳到 lcp 下一个位置进行分治。

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,k;
string a,b;
int base[300010],hsh[300010];
int get_hsh(int l,int r)
{
	return (hsh[r]-1ll*hsh[l-1]*base[r-l+1]%mod+mod)%mod;
}
int get_lcp(int x,int y)
{
	int el=1,er=k,ans=0;
	while(el<=er)
	{
		int mid=el+er>>1;
		if(get_hsh(x,x+mid-1)==get_hsh(y,y+mid-1)) ans=mid,el=mid+1;
		else er=mid-1;
	}
	return ans;
}
long long dfs(int now,vector<int> veca,vector<int> vecb)
{
	if(veca.empty() || vecb.empty()) return 0;
	vector<int> gta[26],gtb[26];
	int lcp=k,lstwz=0;
	for(int i:veca)
	{
		if(lstwz!=0) lcp=min(lcp,get_lcp(lstwz,i));
		lstwz=i;
	}
	for(int i:vecb) lcp=min(lcp,get_lcp(lstwz,i+n)),lstwz=i+n;
	if(lcp==k) return 1ll*k*min(veca.size(),vecb.size());
	for(int i:veca) gta[a[i+lcp]-'a'].push_back(i);
	for(int i:vecb) gtb[b[i+lcp]-'a'].push_back(i);
	long long ans=0; int cnta=0,cntb=0;
	for(int i=0; i<26; ++i)
	{
		ans+=dfs(lcp+1,gta[i],gtb[i]);
		int in=min(gta[i].size(),gtb[i].size());
		cnta+=gta[i].size()-in,cntb+=gtb[i].size()-in;
	}
	return ans+1ll*lcp*min(cnta,cntb);
}
int main()
{
	base[0]=1; for(int i=1; i<=3e5; ++i) base[i]=base[i-1]*131ll%mod;
	cin>>n>>k>>a>>b; a=' '+a,b=' '+b;
	for(int i=1; i<=2*n; ++i) hsh[i]=(hsh[i-1]*131ll+(i<=n?a[i]:b[i-n]))%mod;
	vector<int> veca,vecb;
	for(int i=1; i<=n-k+1; ++i) veca.push_back(i),vecb.push_back(i);
	cout<<1ll*k*(n-k+1)-dfs(0,veca,vecb);
	return 0;
}