【洛谷P3082】【USACO13MAR】—项链Necklace（Kmp+DP）

传送门

$f[i][j]$表示走到第一个的$i$，第二个的$j$的最少删去
用$Ac$自动机的$nxt$转移一下就可以了

#include
using namespace std;
const int RLEN=1<<20|1;
inline char gc(){static char ibuf[RLEN],*ib,*ob;(ob==ib)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));return (ob==ib)?EOF:*ib++;
}
#define gc getchar
inline int read(){char ch=gc();int res=0,f=1;while(!isdigit(ch))f^=ch=='-',ch=gc();while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();return f?res:-res;
}
#define ll long long
#define re register
#define pii pair
#define fi first
#define se second
#define pb push_back
#define cs const
#define bg begin
#define poly vector
#define chemx(a,b) ((a)<(b)?(a)=(b):0)
#define chemn(a,b) ((a)>(b)?(a)=(b):0)
cs int N=10005,M=1005;
int f[N][M],n,m,nxt[M][26],fail[M];
char a[N],b[N];
int main(){scanf("%s",a+1),scanf("%s",b+1);n=strlen(a+1),m=strlen(b+1);memset(f,127/3,sizeof(f));f[0][0]=0;for(int i=0;i<m;i++)nxt[i][b[i+1]-'a']=i+1;for(int i=1;i<=m;i++)for(int j=0;j<26;j++){if(nxt[i][j])fail[nxt[i][j]]=nxt[fail[i]][j];else nxt[i][j]=nxt[fail[i]][j];}for(int i=1;i<=n;i++)for(int j=0;j<m;j++){chemn(f[i][j],f[i-1][j]+1);chemn(f[i][nxt[j][a[i]-'a']],f[i-1][j]);}int res=1e9;for(int i=0;i<m;i++)chemn(res,f[n][i]);cout<<res;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！