AcWing 1053. 修复DNA 题解（状态机DP、AC自动机）

AcWing 1053. 修复DNA
状态机DPS，用ac自动机建立状态机

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

int tr[N][4], dar[N], q[N];
int n, m;
int f[N][N];  //f[i][j]表示长度为i的字符到达第j个字符的最小步数
int get_num[128];  // 数组优化get
char str[N];
int ids;
int ne[N];

void insert(){
    
	int p = 0;
	for(int i = 0; str[i]; i ++ ){
    
		int t = get_num[str[i]];
		if(!tr[p][t]) tr[p][t] = ++ ids;
		p = tr[p][t];
	}
	dar[p] = 1;  //标记病毒结尾 
} 

void build(){
    
	int hh = 0, tt = -1;
	for(int i = 0; i < 4; i ++ ){
    
		if(tr[0][i]) q[ ++ tt] = tr[0][i];
	}
	
	while(hh <= tt){
    
		int t = q[hh ++ ];
		
		for(int i = 0; i < 4; i ++ ){
    
			int p = tr[t][i];
			if(!p) tr[t][i] = tr[ne[t]][i];
			else{
    
				ne[p] = tr[ne[t]][i];
				q[ ++ tt] = p;
				dar[p] |= dar[ne[p]];// 加上这行因为某序列的子序列可能包含了病毒序列
				                     // 比如accgt和cg
			}
		}
	}
}

int main()
{
    
	get_num['A'] = 0;
	get_num['G'] = 1;
	get_num['C'] = 2;
	get_num['T'] = 3;
	int T = 1;
	
	while(cin>>n, n){
    
		memset(ne, 0, sizeof ne);
		memset(tr, 0, sizeof tr);
		memset(dar, 0, sizeof dar);
		ids = 0;

		for(int i = 0; i < n; i ++ ){
    
			cin>>str;
			insert();
		}
		
		build();
		
		scanf("%s", str + 1);
		int len = strlen(str + 1);
		
		
		// 任何trie图里面的idx都可能是路径的终点
	    // f[i][j] 表示的是走到字符串第i个字符, 终点停在j的代价最小的走法, 
		// 而且在这堆走法里面这个字符有可能被改变了也有可能没变
		
		// 从f[0][0] 出发, 也就从idx为0能到的节点被成功min了
		// 然后再从那些成功被min的点才能继续往后走
		memset(f, 0x3f, sizeof f);
		f[0][0] = 0;  //初始修改次数为0 
		
		for(int i = 0; i < len; i ++ ){
      //枚举长度 
			for(int j = 0; j <= ids; j ++ ){
      //j从根节点0开始 
				if(dar[j]) continue;
				if(i && f[i][j] == 0x3f3f3f3f) continue;  // 不能到这种点, 自然也不能从这种点出发
				
				// 从i到i+1, 就是再往前走一个字符, 那么自然我们就只能从已经能走到的点出发,
				// 那么他们的f值就肯定不是无穷
				for(int k = 0; k < 4; k ++ ){
    
					// 判断下个字符是不是当前k, 
                    // 若果是的话, 那么就表示当前字符不需要更改就能往下走, 这一步的t = 0; 
                    // 如果不是k的话, 要往k这个点走, 则需要更改, 这一步的代价t等于1
                    // 注意更改的是str 
					int t = get_num[str[i + 1]] != k;
					
					int p = tr[j][k];
					if(!dar[p]){
    
						// 有标记的点都是不能走的
                        // 从字符str[i]到str[i+1], 从所有的idx(也就是j)各自的4条路里面合法的路径,
                        // 走一步, 选其中代价最小的
						f[i + 1][p] = min(f[i + 1][p], f[i][j] + t);
					}
				}
			}
		}
		int ikt = 0x3f3f3f3f;
		for(int i = 0; i <= ids; i ++ ) ikt = min(ikt, f[len][i]);
		if(ikt == 0x3f3f3f3f) ikt = -1;
		cout<<"Case "<<T ++ <<": "<<ikt<<endl;
		
	}
	return 0;
}