poj 1699 Best Sequence(AC自动机+状压DP)

题目链接：poj 1699 Best Sequence

题目大意；给定N个DNA序列，问说最少多长的字符串包含所有序列。

解题思路：AC自动机+状压DP，先对字符串构造AC自动机，然后在dp[s][i]表示匹配了s，移动到节点i时候的最短步数。

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std; typedef pair
         
           pii; const int maxn = 205; const int sigma_size = 4; const int inf = 0x3f3f3f3f; struct Aho_Corasick { int sz, g[maxn][sigma_size]; int tag[maxn], fail[maxn], last[maxn]; int dp[maxn][1030]; void init(); int idx(char ch); void insert(char* str, int k); void getFail(); void match(char* str); void put(int x, int y); int solve(); }AC; int N; char w[30]; int main () { int cas; scanf("%d", &cas); while (cas--) { AC.init(); scanf("%d", &N); for (int i = 0; i < N; i++) { scanf("%s", w); AC.insert(w, i); } printf("%d\n", AC.solve()); } return 0; } int Aho_Corasick::solve() { getFail(); memset(dp, inf, sizeof(dp)); dp[0][0] = 0; queue
          
            que; que.push(make_pair(0, 0)); while(!que.empty()) { int u = que.front().first; int s = que.front().second; que.pop(); for (int i = 0; i < 4; i++) { int k = u; while (k && g[k][i] == 0) k = fail[k]; k = g[k][i]; int ss = s | tag[k]; if (dp[k][ss] > dp[u][s] + 1) { dp[k][ss] = dp[u][s] + 1; que.push(make_pair(k, ss)); if (ss == (1<
           
             que; for (int i = 0; i < sigma_size; i++) { int u = g[0][i]; if (u) { fail[u] = last[u] = 0; que.push(u); } } while (!que.empty()) { int r = que.front(); que.pop(); for (int i = 0; i < sigma_size; i++) { int u = g[r][i]; if (u == 0) { g[r][i] = g[fail[r]][i]; continue; } que.push(u); int v = fail[r]; while (v && g[v][i] == 0) v = fail[v]; fail[u] = g[v][i]; tag[u] |= tag[fail[u]]; //last[u] = tag[fail[u]] ? fail[u] : last[fail[u]]; } } }