BZOJ3075[USACO 2013 Mar Gold 3.Necklace]——AC自动机+DP

题目描述

给你一个长度为n的字符串A，再给你一个长度为m的字符串B，求至少在A中删去多少个字符才能使得B不是A的子串。注：该题只读入A和B，不读入长度，先读入A，再读入B。数据保证A和B中只含小写字母。

样例输入

ababaa
aba

样例输出

1

样例解释：
ababaa -> abbaa

提示

数据范围：
 n<=10000, m<=1000, m<=n

 

据说这道题用KMP也能写。

首先如果用AC自动机做这道题显然要把B串建在AC自动机上(AC自动机上就一个串好像有点浪费qwq)。要想B串不出现在A串中，只要把A串在AC自动机上跑，使它一直不遍历到B串的终止节点就能保证B串不是A串的子串。想要最优解自然要dp，那么就可以定义f[i][j]表示A串的第i个字符匹配到了AC自动机上第j个节点保留的最长长度。对于A串上的每一个字符可以删除或者在AC自动机上往下走，最后用A串总长len减掉max{f[len][i]}就是最小删除数了。

最后附上代码。

#include<cmath> #include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int cnt; char s[1010]; char t[100010]; int end[1010]; int fail[1010]; int a[1010][26]; int f[10010][1010]; void build(char *s) {int len=strlen(s);int now=0;for(int i=0;i<len;i++){if(!a[now][s[i]-'a']){a[now][s[i]-'a']=++cnt;}now=a[now][s[i]-'a'];}end[now]=1; } void getfail() {queue<int>q;for(int i=0;i<26;i++){if(a[0][i]){q.push(a[0][i]);fail[a[0][i]]=0;}}while(!q.empty()){int now=q.front();q.pop();for(int i=0;i<26;i++){if(a[now][i]){fail[a[now][i]]=a[fail[now]][i];q.push(a[now][i]);} else{a[now][i]=a[fail[now]][i];}}} } int main() {scanf("%s",t);scanf("%s",s);build(s); getfail();memset(f,-1,sizeof(f));int l=strlen(t);f[1][0]=0;f[1][a[0][t[0]-'a']]=1;for(int i=1;i<l;i++){for(int j=0;j<=cnt;j++){if(f[i][j]!=-1){if(!end[a[j][t[i]-'a']]){f[i+1][a[j][t[i]-'a']]=max(f[i+1][a[j][t[i]-'a']],f[i][j]+1);}if(!end[j]){f[i+1][j]=max(f[i+1][j],f[i][j]);}}}}int ans=0;for(int i=0;i<=cnt;i++){if(!end[i]&&f[l][i]!=-1) {ans=max(ans,f[l][i]);}}printf("%d",l-ans); }

转载于:https://www.cnblogs.com/Khada-Jhin/p/9181960.html

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的BZOJ3075[USACO 2013 Mar Gold 3.Necklace]——AC自动机+DP的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。