1. 首页
2. AC自动机, DP
3. 本页

UVALive 7648 Passwords (AC自动机 + DP)

题意：~

思路：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template <class T> inline bool scan_d(T &ret) {char c; int sgn;if(c=getchar(),c==EOF) return 0;while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1;ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn;return 1;}

struct Trie {
    int next[1050][26],fail[1050],end[1050];
    int root,L;
    int newnode()
    {
        for(int i = 0;i < 26;i++) next[L][i] = -1;
        end[L++] = 0;
        return L-1;
    }
    void init()
    {
        L = 0;
        root = newnode();
    }
    void insert(char buf[])
    {
        int len = (int)strlen(buf);
        int now = root;
        for(int i = 0;i < len;i++)
        {
            if(next[now][buf[i]-'a'] == -1)
                next[now][buf[i]-'a'] = newnode();
            now = next[now][buf[i]-'a'];
        }
        end[now]++;
    }
    void build()
    {
        queue<int>Q;
        fail[root] = root;
        for(int i = 0;i < 26;i++)
            if(next[root][i] == -1)
                next[root][i] = root;
            else
            {
                fail[next[root][i]] = root;
                Q.push(next[root][i]);
            }
        while(!Q.empty())
        {
            int now = Q.front();
            Q.pop();
            if(end[fail[now]]) end[now]++;
            for(int i = 0;i < 26;i++)
                if(next[now][i] == -1)
                {
                    next[now][i] = next[fail[now]][i];
                }
                else
                {
                    fail[next[now][i]] = next[fail[now]][i];
                    Q.push(next[now][i]);
                }
        }
    }
};

inline int cag(int x)
{
    if(x == 0) return 'o' - 'a';
    if(x == 1) return 'i' - 'a';
    if(x == 3) return 'e' - 'a';
    if(x == 5) return 's' - 'a';
    if(x == 7) return 't' - 'a';
    return - 1;
}

Trie ac;
const int mod = 1000003;
int dp[25][1005][10];
char str[25];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int l, r;
    while(cin >> l >> r)
    {
        int m;
        cin >> m;
        ac.init();
        for(int i = 0; i < m; ++i)
        {
            cin >> str;
            ac.insert(str);
        }
        ac.build();
        memset(dp, 0, sizeof(dp));
        dp[0][0][0] = 1;
        for(int i = 0; i < r; ++i)
        {
            for(int j = 0; j < ac.L; ++j)
            {
                for(int k = 0; k < 8; ++k)
                {
                    if(dp[i][j][k] == 0) continue;
                    int last = dp[i][j][k];
                    int sta = 0;
                    for(int t = 0; t < 26; ++t)
                    {
                        int c = ac.next[j][t];
                        if(ac.end[c]) continue;
                        sta = k | 1;
                        dp[i + 1][c][sta] = (dp[i + 1][c][sta] + last) % mod;
                        sta = k | 2;
                        dp[i + 1][c][sta] = (dp[i + 1][c][sta] + last) % mod;
                    }
                    sta = k | 4;
                    for(int t = 0; t < 10; ++t)
                    {
                        int c = cag(t);
                        if(c == -1)
                            dp[i + 1][0][sta] = (dp[i + 1][0][sta] + last) % mod;
                        else
                        {
                            c = ac.next[j][c];
                            if(ac.end[c]) continue;
                            dp[i + 1][c][sta] = (dp[i + 1][c][sta] + last) % mod;
                        }
                    }
                }
            }
        }
        int ans = 0;
        for(int i = l; i <= r; ++i)
        {
            for(int j = 0; j < ac.L; ++j)
                ans = (ans + dp[i][j][7]) % mod;
        }
        cout << ans << "\n";
    }
    return 0;
}