AcWing 1053. Repair DNA problem solution (state machine DP, AC automata)

AcWing 1053. 修复DNA
状态机DPS,用acAn automaton builds a state machine

#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]表示长度为iThe characters reach the thj个字符的最小步数
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;  //Mark the end of the virus 
} 

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]];// Add this line because a subsequence of a sequence may contain a viral sequence
				                     // 比如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图里面的idxmay be the end of the path
	    // f[i][j] It means to go to the first stringi个字符, stop atjthe least expensive move, 
		// And in this pile of moves, the character may or may not have been changed
		
		// 从f[0][0] 出发, 也就从idx为0The nodes that can be reached are successfulmin了
		// Then again from those that succeededminpoint to continue going backwards
		memset(f, 0x3f, sizeof f);
		f[0][0] = 0;  //The initial number of modifications is 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;  // Can't get to that point, Naturally, we cannot start from this point
				
				// 从i到i+1, Just go one character further, Then naturally we can only start from the point where we can already go,
				// 那么他们的fThe value is definitely not infinite
				for(int k = 0; k < 4; k ++ ){
    
					// Determine if the next character is the current onek, 
                    // If so, Then it means that the current character can go down without changing, 这一步的t = 0; 
                    // 如果不是k的话, 要往k这个点走, 则需要更改, the cost of this stept等于1
                    // Note that the change isstr 
					int t = get_num[str[i + 1]] != k;
					
					int p = tr[j][k];
					if(!dar[p]){
    
						// Marked points are not allowed to go
                        // 从字符str[i]到str[i+1], 从所有的idx(也就是j)各自的4A legal path inside the road,
                        // 走一步, Choose the least expensive of them
						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;
}