題目描述

給你一個長度為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的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。