传送门
题意简述：给出S,TS,TS,T两个字串，∣S∣≤10000,∣T∣≤1000|S|\le10000,|T|\le1000∣S∣≤10000,∣T∣≤1000，问至少从SSS中删去几个字符能够使得TTT不是修改后的SSS的字串。
思路：
考虑正难则反转化问题。
只需要求所有使得TTT不为SSS字串的SSS的字符数最大值。
于是设计状态fi,jf_{i,j}fi,j表示SSS中前iii个字符匹配上TTT的第jjj位可保留的最多字符数。
然后考虑当前这一位删不删转移就行了。
可以用kmpkmpkmp来优化转移，时间复杂度O(nm)O(nm)O(nm)
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=10005,M=1005;
char s[N],t[M];
int tmp=0,ans=0,f[2][M],n,m,fail[M];
int main(){
scanf("%s%s",s+1,t+1),n=strlen(s+1),m=strlen(t+1);
for(ri i=1,j=0;i<=m;++i){
while(j&&t[i+1]!=t[j+1])j=fail[j];
fail[i+1]=t[i+1]==t[j+1]?++j:0;
}
memset(f[tmp],-1,sizeof(f[tmp]));
f[tmp][0]=0;
for(ri i=1;i<=n;++i){
memset(f[tmp^1],-1,sizeof(f[tmp^1]));
for(ri j=0,k;j<m;++j)if(~f[tmp][j]){
f[tmp^1][j]=max(f[tmp^1][j],f[tmp][j]);
k=j;
while(k&&s[i]!=t[k+1])k=fail[k];
if(s[i]==t[k+1])++k;
f[tmp^1][k]=max(f[tmp^1][k],f[tmp][j]+1);
}
tmp^=1;
}
for(ri i=0;i<m;++i)ans=max(ans,f[tmp][i]);
cout<<n-ans;
return 0;
}