uva 1076 - Password Suspects(AC自動機+記憶化搜索)

uva 1076 - Password Suspects(AC自動機+記憶化搜索)

題目鏈接：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]];
        }
    }
}