Wireless Password

Time limit:1000ms Memory limit:32768kB

链接

http://acm.hdu.edu.cn/showproblem.php?pid=2825

题意

给出m个单词,问长度为n的字符串中含有至少k个给出的单词一共有多少?(‘a’-‘z’)

思路

题解

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;

typedef long long ll;

const ll mod = 20090717;
const int kind = 26;
const int maxn = 105;

int root, cnt;
int nxt[maxn][kind];
int fail[maxn];
int state[maxn];

int newnode ()
{
    ++cnt;
    for (int i = 0; i < kind; ++i) {
        nxt[cnt][i] = -1;
    }
    state[cnt] = 0;
    return cnt;
}

void ac_init ()
{
    cnt = -1;
    root = newnode();
}

void wd_insert (char str[], int p)
{
    int len = strlen(str);
    int now = root;
    for (int i = 0; i < len; ++i) {
        if (nxt[now][str[i]-'a'] == -1) {
            nxt[now][str[i]-'a'] = newnode();
        }
        now = nxt[now][str[i]-'a'];
    }
    state[now] = (1<<(p-1));
}

void build ()
{
    queue<int> q;
    fail[root] = root;
    for (int i = 0; i < kind; ++i) {
        if (nxt[root][i] == -1) {
            nxt[root][i] = root;
        }
        else {
            fail[nxt[root][i]] = root;
            q.push(nxt[root][i]);
        }
    }
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        state[now] |= state[fail[now]];
        for (int i = 0; i < kind; ++i) {
            if (nxt[now][i] == -1) {
                nxt[now][i] = nxt[fail[now]][i];
            }
            else {
                fail[nxt[now][i]] = nxt[fail[now]][i];
                q.push(nxt[now][i]);
            }
        }
    }
}

int num[1<<10];

void init ()
{
    for (int i = 0; i < (1<<10); ++i) {
        int tmp = 0;
        int d = i;
        while (d) {
            tmp += (d&1);
            d >>= 1;
        }
        num[i] = tmp;
    }
}

int n, m, k;
char str[15];

int dp[26][105][(1<<10)];

int main ()
{
    init();
    while (scanf("%d %d %d", &n, &m, &k) != EOF && n+m+k) {
        ac_init();
        for (int i = 1; i <= m; ++i) {
            scanf("%s", str);
            wd_insert(str, i);
        }
        build();
        memset(dp, 0, sizeof(dp));
        dp[0][0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= cnt; ++j) {
                for (int l = 0; l < (1<<m); ++l) {
                    if (dp[i-1][j][l] == 0) {
                        continue;
                    }
                    for (int p = 0; p < kind; ++p) {
                        dp[i][nxt[j][p]][l|state[nxt[j][p]]] += dp[i-1][j][l];
                        dp[i][nxt[j][p]][l|state[nxt[j][p]]] %= mod;
                    }
                }
            }
        }
        int res = 0;
        for (int l = 0; l < (1<<m); ++l) {
            if (num[l] >= k) {
                for (int j = 0; j <= cnt; ++j) {
                    res += dp[n][j][l];
                    res %= mod;
                }
            }
        }
        cout << res << '\n';
    }
    return 0;
}

发表评论