给你长度相同的两个字符串 \(s\) 和 \(t\) ，每次操作可以把 \(s\) 中一个字符移到前面的任意位置，求最少经过多少次操作使得 \(s\) 和 \(t\) 相等；
如果操作是可以把 \(s\) 中一个字符任意移动，那不难想到最少操作次数即（字符串的长度 - s和t的最长公共子序列） ，而现在只能往前移动，那么此时需要求的 最长公共子序列 就需要有额外条件；我们知道最长公共子序列之间一一对应，对于 \(s[i]\) 和 \(t[j]\) ，若 \(s[i]=t[j]\) 且为最长公共子序列的其中一个对应 ，则串 \(s\) 中 \(i\) 后面的字符要么是最长公共子序列的一部分，要么只能往前移动到 \(i\) 前面，而字符串 \(t\) 是固定不变的，所以串 \(t\) 中 \(j\) 后面的字符肯定全包括在串 \(s\) 中 \(i\) 后面，即 \(t[j+1...n] \in s[i+1...n]\) ，这样子就可以匹配只能往前移动的操作了；
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define frep(i,a,b) for(int i=a;i>=b;i--)
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T,n;
string s,t;
cin>>T;
while(T--)
{
cin>>n>>s>>t;
s=‘.‘+s;
t=‘.‘+t;
vector<vi>dp(n+1,vi(n+1)); //dp[i][j]表示s[1...i]和t[1...j]的最长公共子序列
vector<vi>suf_s(n+2,vi(26)),suf_t(n+2,vi(26)); //后缀
frep(i,n,1)
{
rep(k,0,25)
suf_s[i][k]=suf_s[i+1][k],
suf_t[i][k]=suf_t[i+1][k];
++suf_s[i][s[i]-‘a‘];
++suf_t[i][t[i]-‘a‘];
}
bool ok=1;
rep(i,0,25)if(suf_s[1][i]!=suf_t[1][i])ok=0; //某种字符数量不相等，无解
if(!ok){cout<<-1<<endl;continue;}
dp[0][0]=0;
rep(i,1,n)rep(j,i,n)
{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
if(s[i]==t[j])
{
ok=1;
//等价于判断 s[i+1...n] 中是否包括 t[j+1...n]
rep(k,0,25)if(suf_s[i+1][k]<suf_t[j+1][k])ok=0;
if(ok)dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
}
}
cout<<n-dp[n][n]<<endl;
}
}
把操作分为两部分，提取和插入，其中 提取 需要花费代价而 插入 不需要，设 \(dp[i][j]\) 表示 \(s\) 串匹配到第 \(i\) 个字符，而 \(t\) 串对应匹配到第 \(j\) 个字符 耗费的最少代价；这里匹配的含义是指通过 \(s\) 串前 \(i\) 个字符内的若干前移 (提取+插入) 操作，和 \(i\) 后面若干字符移动到 \(i\) 前面，从而匹配 \(t[1...j]\)，因为我们设定插入不需要代价，所以 \(dp[i][j]\) 计算的代价实际上是前 \(i\) 个字符内的若干前移的代价； 同时可以清楚 \(i \leq j~and~s[1...i] \in t[1...j]\) ；
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define frep(i,a,b) for(int i=a;i>=b;i--)
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T,n;
string s,t;
cin>>T;
while(T--)
{
cin>>n>>s>>t;
s=‘.‘+s;
t=‘.‘+t;
vector<vi>dp(n+1,vi(n+1));
vector<vi>suf_s(n+2,vi(26)),suf_t(n+2,vi(26));
frep(i,n,1)
{
rep(k,0,25)
suf_s[i][k]=suf_s[i+1][k],
suf_t[i][k]=suf_t[i+1][k];
++suf_s[i][s[i]-‘a‘];
++suf_t[i][t[i]-‘a‘];
}
bool ok=1;
rep(i,0,25)if(suf_s[1][i]!=suf_t[1][i])ok=0; //无解的情况
if(!ok){cout<<-1<<endl;continue;}
dp[0][0]=0;
rep(i,1,n)rep(j,i,n)
{
int x=dp[i-1][j]+1; // 1：提取第i个字符的代价
if(s[i]==t[j])x=min(x,dp[i-1][j-1]); // 2：s[i]=t[j]，则直接匹配
if(suf_s[i+1][t[j]-‘a‘]>suf_t[j+1][t[j]-‘a‘]) x=min(x,dp[i][j-1]); // 3
dp[i][j]=x;
}
cout<<dp[n][n]<<endl;
}
}
解法3和解法2其实差不多，将 \(s\) 和 \(t\) 反转，那么前移操作就变成了后移操作，同样把操作分为两部分，提取和插入，其中 提取 需要花费代价而 插入 不需要；设 \(dp[i][j]\) 表示 \(s\) 串匹配到第 \(i\) 个字符，而 \(t\) 串对应匹配到第 \(j\) 个字符 耗费的最少代价（\(s\) 串前 \(i\) 个字符多余的提取出来，后面可以无代价插入），同理 \(i \geq j~and~t[1...j] \in s[1...i]\) ；
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define frep(i,a,b) for(int i=a;i>=b;i--)
const int N = 2000+2;
int pre_s[N][26],pre_t[N][26];
bool OK(int i,int j){ //判断s串前i个字符是不是包含t串前j个字符
rep(k,0,25)
if(pre_s[i][k]<pre_t[j][k])return false;
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T,n;
string s,t;
cin>>T;
while(T--)
{
cin>>n>>s>>t;
reverse(s.begin(),s.end());
reverse(t.begin(),t.end());
s=‘.‘+s;
t=‘.‘+t;
vector<vi>dp(n+1,vi(n+1));
memset(pre_s,0,sizeof(pre_s));
memset(pre_t,0,sizeof(pre_t));
rep(i,1,n)
{
rep(k,0,25)
pre_s[i][k]=pre_s[i-1][k],
pre_t[i][k]=pre_t[i-1][k];
++pre_s[i][s[i]-‘a‘];
++pre_t[i][t[i]-‘a‘];
}
bool ok=1;
rep(i,0,25)if(pre_s[n][i]!=pre_t[n][i])ok=0;
if(!ok){cout<<-1<<endl;continue;}
rep(i,0,n)dp[i][0]=i; //初始化
rep(i,1,n)rep(j,1,i)
{
if(!OK(i,j))continue;
dp[i][j]=dp[i][j-1];
if(OK(i-1,j))dp[i][j]=min(dp[i][j],dp[i-1][j]+1);
if(s[i]==t[j]) dp[i][j]=min(dp[i][j],dp[i-1][j-1]);
}
cout<<dp[n][n]<<endl;
}
}
Codeforces Round #646 (Div. 2) F. Rotating Substrings
原文：https://www.cnblogs.com/17134h/p/13057750.html