P6793 [SNOI2020]字符串
给出两个长度为\(n\)的字符串\(a,b\)，取出他们所有长为\(k\)的子串（各有\(n-k+1\)个），这些子串分别组成集合\(A,B\)。
现在要修改\(A\)中的串，使得\(A\)和\(B\)完全相同。
可以任意次选择修改\(A\)中的一个串的一段后缀。花费为这段后缀的长度。
总花费为每次修改花费之和。
求总花费的最小值。
做法：
将\(a\)和\(b\)的后\(n-k+1\)个字符倒序插入SAM。
然后建出link树，\(a\)和\(b\)的后缀在树上对应若干个节点。
然后对于两个节点，他们的lca越深匹配效果越好。
因为匹配代价是\(k-len(lca)\)。
问题转化为：
给出树上两个相同的点集。
两个点匹配的代价是\(min(k,dep(lca))\)。
询问怎么匹配，总代价最小。
对每个子树维护两个值：
\(f[u][0]\)表示点集\(A\)剩余未匹配的点数。
\(f[u][1]\)表示点集\(B\)剩余未匹配的点数。
自底向上转移即可。
时间复杂度\(O(n)\)。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int n,k,nxt[maxn][26],link[maxn],len[maxn],dp[maxn][2],tot=1,lst=1;
string A,B;
void sam_extend (char c,int f,int v) {
int cur=++tot,p=lst;
dp[cur][f]=v;
len[cur]=len[lst]+1;
while (p&&!nxt[p][c-'a']) {
nxt[p][c-'a']=cur;
p=link[p];
}
if (!p) link[cur]=1;
else {
int q=nxt[p][c-'a'];
if (len[p]+1==len[q]) link[cur]=q;
else {
int clone=++tot;
len[clone]=len[p]+1;
for (int i=0;i<26;i++) nxt[clone][i]=nxt[q][i];
link[clone]=link[q];
while (p&&nxt[p][c-'a']==q) {
nxt[p][c-'a']=clone;
p=link[p];
}
link[q]=link[cur]=clone;
}
}
lst=cur;
}
vector<int> g[maxn];
long long ans=0;
void dfs (int u) {
for (int v:g[u]) {
dfs(v);
for (int i=0;i<2;i++) dp[u][i]+=dp[v][i];
}
int gg=min(dp[u][0],dp[u][1]);
ans+=1ll*gg*max(0,k-len[u]);
dp[u][0]-=gg;
dp[u][1]-=gg;
}
int main () {
ios::sync_with_stdio(false);
cin>>n>>k;
cin>>A;
cin>>B;
for (int i=n-1;i>=0;i--) {
int ff=0;
if (i<=n-k) ff=1;
sam_extend(A[i],0,ff);
}
lst=1;
for (int i=n-1;i>=0;i--) {
int ff=0;
if (i<=n-k) ff=1;
sam_extend(B[i],1,ff);
}
for (int i=2;i<=tot;i++) {
g[link[i]].push_back(i);
}
dfs(1);
cout<<ans;
}