题目链接：uva 1076 - Password Suspects

题目大意：有一个长度为n的密码，存在m个子串，问说有多少种字符串满足，如果满足个数不大于42，按照字典序输出。

解题思路：根据子串构建AC自动机，然后记忆化搜索，dp[i][u][s]表示第i个字符，在u节点，匹配s个子串。

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           using namespace std; typedef long long ll; const int maxn = 105; const int maxs = (1<<10)+5; const int sigma_size = 26; struct Aho_Corasick { int sz, g[maxn][sigma_size]; int val[maxn], fail[maxn]; void init(); int idx(char ch); void insert(char* str, int k); void get_fail(); }AC; int N, M; vector
          
            vec; ll dp[30][maxn][maxs]; void init () { AC.init(); char str[20]; for (int i = 0; i < M; i++) { cin >> str; AC.insert(str, i); } AC.get_fail(); memset(dp, -1, sizeof(dp)); } ll solve (int d, int u, int s) { if (d >= N) return s == (1<
           
            = N) { if (s == (1<
            
              que; for (int i = 0; i < sigma_size; i++) { int u = g[0][i]; if (u) { fail[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]; val[u] |= val[fail[u]]; } } }