$给定 n 个模式串，和一个长度为 m 的原串 s，求至少修改原串中的几个字符可以使得原串中不包含任一个模式串。模式串总长度 ≤ 1000，m ≤ 1000。$
先建出模式串的AC自动机，然后考虑怎么求最优解。考虑AC自动机上DP，设$f_{i,j}$走了$i$步之后在$j$节点时候的最少修改次数。
标记处所有不能走到的点（即走到就匹配了的点，即后缀为某一模式串的所有点），走点的时候应当回避这些点，转移的时候向合法的状态转移，分两种。
一种沿着原串$s_i$走，$f_{i+1,to_j}leftarrow f_{i,j}$，另一种是走其他路，$f_{i+1,to_j'}leftarrow f_{i,j}+1$。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #define dbg(x) cerr << #x << " = " << x <<endl 8 using namespace std; 9 typedef long long ll; 10 typedef double db; 11 typedef pair<int,int> pii; 12 template<typename T>inline T _min(T A,T B){return A<B?A:B;} 13 template<typename T>inline T _max(T A,T B){return A>B?A:B;} 14 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,1):0;} 15 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,1):0;} 16 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;} 17 template<typename T>inline T read(T&x){ 18 x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1; 19 while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x; 20 } 21 const int N=1000+7,INF=0x3f3f3f3f; 22 int ha[128],tr[N][4],ban[N],nxt[N],legal[N],cnt,tot; 23 char s[N]; 24 int n; 25 inline void Insert(){ 26 int len=strlen(s+1),x=0; 27 for(register int i=1,c=ha[s[1]];i<=len;++i,c=ha[s[i]]){ 28 if(!tr[x][c])tr[x][c]=++tot; 29 x=tr[x][c]; 30 } 31 ban[x]=1; 32 } 33 queue<int> q; 34 inline void Build(){ 35 legal[cnt=1]=0; 36 memset(nxt,0,sizeof nxt); 37 for(register int i=0;i<4;++i)if(tr[0][i])nxt[tr[0][i]]=0,q.push(tr[0][i]); 38 while(!q.empty()){ 39 int x=q.front();q.pop(); 40 if(ban[nxt[x]])ban[x]=1; 41 if(!ban[x])legal[++cnt]=x; 42 for(register int i=0;i<4;++i) 43 if(tr[x][i])nxt[tr[x][i]]=tr[nxt[x]][i],q.push(tr[x][i]); 44 else tr[x][i]=tr[nxt[x]][i]; 45 } 46 } 47 #define j legal[_] 48 int f[N][N],ans,T; 49 inline void dp(){ 50 memset(f,0x3f,sizeof f); 51 f[0][0]=0;ans=INF; 52 int len=strlen(s+1); 53 for(register int i=0;i<len;++i) 54 for(register int _=1;_<=cnt;++_)if(f[i][j]<INF){ 55 int c=ha[s[i+1]];//dbg(i),dbg(j),dbg(f[i][j]); 56 for(register int k=0;k<4;++k) 57 if(!ban[tr[j][k]]&&(c^k)) 58 MIN(f[i+1][tr[j][k]],f[i][j]+1); 59 if(!ban[tr[j][c]])MIN(f[i+1][tr[j][c]],f[i][j]); 60 } 61 for(register int _=1;_<=cnt;++_)MIN(ans,f[len][j]); 62 } 63 #undef j 64 int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout); 65 ha['A']=0,ha['C']=1,ha['G']=2,ha['T']=3; 66 while(read(n)){ 67 memset(ban,0,sizeof ban);memset(tr,0,sizeof tr),tot=0; 68 for(register int i=1;i<=n;++i)scanf("%s",s+1),Insert(); 69 Build();scanf("%s",s+1);dp(); 70 printf("Case %d: %d ",++T,ans<INF?ans:-1); 71 } 72 return 0; 73 }
总结：AC自动机上DP多为$f_{i,j}$型状态设计，需要考虑每一步各种转移情况。过于浅薄