考研路茫茫――单词情结

Time limit:1000ms Memory limit:32768k

链接

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

题意

给出n个字符串,问有多少种长度最少为1最长m的字符串至少包含一个给出的子串?

思路

之前写的一篇里面有讲一个都不包含的有多少种。那么这个题可以求出总的个数减去一个都不包含的有多少种,不过这次要求的是矩阵的1次方到l次方的和来表示长度从1到l。

代码

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

typedef unsigned long long ll;

const int maxn = 70;
const int kind = 26;

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

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

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

void wd_insert (char str[])
{
    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'];
    }
    mrk[now] = 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();
        mrk[now] |= mrk[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]);
            }
        }
    }
}

char str[10];

struct Matrix
{
    ll mp[maxn][maxn];
    Matrix ()
    {
        memset(mp, 0, sizeof(mp));
    }
};

int dr;

Matrix operator* (const Matrix &m1, const Matrix &m2)
{
    Matrix m;
    for (int i = 0; i <= dr; ++i) {
        for (int j = 0; j <= dr; ++j) {
            for (int k = 0 ; k <= dr; ++k) {
                m.mp[i][j] += m1.mp[i][k]*m2.mp[k][j];
            }
        }
    }
    return m;
}

Matrix matrix_qm (Matrix A, ll b)
{
    Matrix m;
    for (int i = 0; i <= dr; ++i) {
        m.mp[i][i] = 1;
    }
    while (b)
    {
        if (b&1) {
            m = m*A;
        }
        A = A*A;
        b >>= 1;
    }
    return m;
}

int main ()
{
    int n;
    ll m;
    while (scanf("%d %lld", &n, &m) != EOF) {
        init();
        for (int i = 1; i <= n; ++i) {
            scanf("%s", str);
            wd_insert(str);
        }
        build();
        Matrix t, s;
        for (int i = 0; i <= cnt; ++i) {
            if (mrk[i] != 0) {
                continue;
            }
            for (int j = 0; j < kind; ++j) {
                if (mrk[nxt[i][j]] == 0) {
                    ++t.mp[i][nxt[i][j]];
                }
            }
        }
        for (int i = 0; i <= cnt; ++i) {
            s.mp[i][i] = 1;
            for (int j = 0; j <= cnt; ++j) {
                s.mp[i][j+cnt+1] = s.mp[i+cnt+1][j+cnt+1] = t.mp[i][j];
            }
        }
        dr = 2*cnt+1;
        s = matrix_qm(s, m);
        for (int i = 0; i <= 2*cnt+1; ++i) {
            for (int j = 0; j <= 2*cnt+1; ++j) {
                t.mp[i][j] = 0;
            }
        }
        for (int i = 0; i <= cnt; ++i) {
            t.mp[i+cnt+1][i] = 1;
        }
        s = s*t;
        ll res2 = 0;
        for (int i = 0; i <= cnt; ++i) {
            res2 += s.mp[0][i];
        }
        dr = 1;
        s.mp[0][0] = 1, s.mp[0][1] = s.mp[1][1] = 26, s.mp[1][0] = 0;
        s = matrix_qm(s, m);
        ll res1 = s.mp[0][1];
        cout << res1-res2 << '\n';
    }
    return 0;
}

发表评论