題目來源：HDU 2457 DNA repair
題意：給你一個文本串 求最少需要修改的次數 使得文本串不包含模式串
思路：可以一位一位構造一個和文本串長度一樣的字符串 就4個字符 每次4選1 如果對應的位置的字符不一樣修改的次數+1 並且構造的時候不包含禁止節點
dp[i][j] 代表到文本串的前i位 在ac自動機的狀態為j 最少需要修改的次數
dp[l+1][v] = min(dp[l+1][v], dp[l][i] + sum); sum的值為0或1 每次都是當前狀態推後面的狀態 v 是i的後續狀態 v 和 i都不是禁止節點的狀態
#include#include #include #include using namespace std; const int maxnode = 55*22; const int size = 4; int ch[maxnode][size]; int val[maxnode]; int f[maxnode]; int sz; const int maxn = 1010; int dp[maxn][maxnode]; char s[maxn]; void init() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); } int idx(char c) { if(c == 'A') return 0; if(c == 'T') return 1; if(c == 'C') return 2; if(c == 'G') return 3; } void insert(char *s, int v) { int u = 0, n = strlen(s); for(int i = 0; i < n; i++) { int c = idx(s[i]); if(!ch[u][c]) { memset(ch[sz], 0, sizeof(ch[sz])); val[sz] = 0; ch[u][c] = sz++; } u = ch[u][c]; } val[u] = 1; } void getFail() { queue q; f[0] = 0; for(int c = 0; c < 4; c++) { int u = ch[0][c]; if(u) { f[u] = 0; q.push(u); } } while(!q.empty()) { int r = q.front(); q.pop(); for(int c = 0; c < 4; c++) { int u = ch[r][c]; if(!u) { ch[r][c] = ch[f[r]][c]; continue; } q.push(u); int v = f[r]; while(v && !ch[v][c]) v = f[v]; f[u] = ch[v][c]; val[u] |= val[f[u]]; } } } int main() { int cas = 1; int n; while(scanf("%d", &n) && n) { init(); for(int i = 0; i < n; i++) { char s[22]; scanf("%s", s); insert(s, 1); } getFail(); scanf("%s", s); memset(dp, -1, sizeof(dp)); int ans = 999999999; dp[0][0] = 0; n = strlen(s); for(int l = 0; l < n; l++) { for(int i = 0; i < sz; i++) { if(val[i] || dp[l][i] == -1) continue; for(int j = 0; j < 4; j++) { if(val[ch[i][j]]) continue; int v = ch[i][j]; int sum = 0; if(idx(s[l]) != j) sum++; if(dp[l+1][v] == -1) dp[l+1][v] = dp[l][i] + sum; else dp[l+1][v] = min(dp[l+1][v], dp[l][i] + sum); if(l + 1 == n) ans = min(ans, dp[l+1][v]); } } } printf("Case %d: ", cas++); if(ans == 999999999) printf("-1\n"); else printf("%d\n", ans); } return 0; }
