hdu 3247 Resource Archiver(AC自动机+BFS+DP)

题目链接：hdu 3247 Resource Archiver

题目大意：给定N个需要包含的串，M个不能包含的串，问说满足的最短字符串长度。

解题思路：直接对所有串建立AC自动机，不能满足的串用同一种标记即可。然后处理出所有属于需要包含串的单词节

点，用BFS处理出两两之间的距离，并且过程中是不能经过禁止节点。这样做的原因是节点的个数很多，如果对所有的

节点进行dp的话空间都不够。剩下的就是dp了。

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          using namespace std; typedef pair
         
           pii; const int maxn = 100005; const int maxm = 1005; const int sigma_size = 2; const int inf = 0x3f3f3f3f; struct Aho_Corasick { int sz, g[maxn][sigma_size]; int tag[maxn], fail[maxn], vis[maxn]; void init(); int idx(char ch); void insert(char* str, int k); void getFail(); void match(char* str); void put(int x, int y); queue
          
            que; int K, pos[maxm], dis[maxn]; int dp[maxm][1030], d[maxm][maxm]; int solve(); void BFS(int s); int DP(); }AC; int N, M; char w[1005]; int main () { while (scanf("%d%d", &N, &M) == 2 && N + M) { AC.init(); for (int i = 1; i <= N; i++) { scanf("%s", w); AC.insert(w, i); } for (int i = 1; i <= M; i++) { scanf("%s", w); AC.insert(w, 0); } printf("%d\n", AC.solve()); } return 0; } int Aho_Corasick::DP() { int E = (1<
           
            >1); dp[v][s] = min(dp[v][s], dp[u][i] + d[u][v]); } } } int ans = inf; for (int i = 0; i < K; i++) ans = min(ans, dp[i][E]); return ans; } void Aho_Corasick::BFS(int s) { memset(dis, inf, sizeof(dis)); dis[pos[s]] = 0; que.push(pos[s]); while (!que.empty()) { int u = que.front(); que.pop(); for (int i = 0; i < sigma_size; i++) { int t = u; while (t && g[t][i] == 0) t = fail[t]; t = g[t][i]; if (tag[t]&1) continue; if (dis[t] > dis[u] + 1) { dis[t] = dis[u] + 1; que.push(t); } } } for (int i = 0; i < K; i++) d[s][i] = dis[pos[i]]; } int Aho_Corasick::solve() { getFail(); K = 0; pos[K++] = 0; for (int i = 1; i 
            
             >1) pos[K++] = i; } for (int i = 0; i < K; i++) BFS(i); return DP(); } void Aho_Corasick::init() { sz = 1; tag[0] = 0; memset(g[0], 0, sizeof(g[0])); } int Aho_Corasick::idx(char ch) { return ch - '0'; } void Aho_Corasick::put(int x, int y) { } void Aho_Corasick::insert(char* str, int k) { int u = 0, n = strlen(str); for (int i = 0; i < n; i++) { int v = idx(str[i]); if (g[u][v] == 0) { vis[sz] = tag[sz] = 0; memset(g[sz], 0, sizeof(g[sz])); g[u][v] = sz++; } u = g[u][v]; } tag[u] = (1<