hyz's blog
0%

HDU 2243 考研路茫茫――单词情结 题解

发表于

题意

给了n($0 < n < 6$)个模式串，需要求至少包含一个模式串、长度最长为L($ 0 < L < 2^{31} $)的字符串数。

分析

注意到是多模式串匹配问题，所以考虑用AC自动机。又因为至少包含一个模式串的问题不太好直接求解，因此我们将其转化为求一个模式串都不包含的问题。我们用模式串建立AC自动机，每个模式串最终走到的节点是不合法的，且假如它的失配指针指向的节点是不合法的话，它也是不合法的，因为它指向的节点是它的一个后缀。然后，假设AC自动机的节点个数为$L$，那么我们就可以建立一个$ L * L $的方案矩阵，这个矩阵的$mat[i][j]$表示$i$到$j$的合法方案数，将这个矩阵求$n$次幂，就得到了走$n$步的方案矩阵。但是由于我们需要求走了$1$ ~ $n$步的方案数，所以需要求和，需要给矩阵最右端增加一列，全置为1，那么第一行最后一列的值减去1就是走了$1$ ~ $n-1$步的方案数。至于字符串总数，也是可以通过构造矩阵求解的，具体构造方法请参考代码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const long double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double Eps = 1e-7;
const int N = 1e5+9;

/************************************************************/
/* 矩阵快速幂：根据递推式快速计算第n项(Untested)
 * 矩阵构造、时间复杂度参考白书P201
 */

// 定义矩阵元素为long long的矩阵：
typedef vector<ull> vll;
typedef vector<vll> mat;

mat mul(mat A, mat B){
    mat C(A.size(), vll(B[0].size(), 0));	
    for(int i = 0; i < A.size(); i++)
        for(int k = 0; k < A[0].size(); k++)
            for(int j = 0; j < B[0].size(); j++)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]);
    return C;
}

mat pow(mat A, ll n) {
    mat B(A.size(), vll(A.size(), 0));		
    for(int i = 0; i < B.size(); i++)
        B[i][i] = 1;
    while(n) {
        if(n & 1) B = mul(B, A);
        A = mul(A, A);
        n >>= 1;
    }
    return B;
}

/************************************************************/

/********************************************************************************/
/* AC自动机：解决多个模式串匹配问题(Tested 1 times)
 */
struct AC {
    int next[39][26], fail[39], end[39], idx, root;
    void init() {
        idx = 0;
        root = newNode();
    }
    int newNode() {
        for(int i = 0; i < 26; i++)
            next[idx][i] = -1;
        end[idx] = false;
        return idx++;
    }
    void insert(char s[]) {
        int len = strlen(s), now = root;
        for(int i = 0; i < len; i++) {
            if(next[now][s[i] - 'a'] == -1)
                next[now][s[i] - 'a'] = newNode();
            now = next[now][s[i] - 'a'];
        }
        end[now] = true;	//根据实际情况可能需要保存不同的信息
    }
    void build() {
        queue<int> que;
        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;
                que.push(next[root][i]);
            }
        }
        while(que.size()) {
            int now = que.front();
            que.pop();
            if(end[fail[now]] == true)
                end[now] = true;
            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];
                    que.push(next[now][i]);
                }
            }
        }
    }
    ull cntIllegal(ll L) {
        mat a(idx + 1, vll(idx + 1, 0));
        for(int i = 0; i < idx; i++)
            for(int j = 0; j < 26; j++)
                if(end[next[i][j]] == false)
                    a[i][next[i][j]]++;
        for(int i = 0; i < idx + 1; i++)
            a[i][idx] = 1;
        a = pow(a, L);
        ull ans = 0;
        for(int i = 0; i < idx + 1; i++)
            ans += a[0][i];
        return ans - 1;
    }
}ac;
/********************************************************************************/

int n;
ll L;
char s[N];

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(~scanf("%d%lld", &n, &L)) {
        ac.init();
        while(n--) {
            scanf("%s", s);
            ac.insert(s);
        }
        mat a(2, vll(2, 0)), b(2, vll(1, 0));
        a[0][0] = 26, a[0][1] = 1;
        a[1][0] = 0, a[1][1] = 1;
        b[0][0] = 1;
        b[1][0] = 1;
        a = pow(a, L);
        a = mul(a, b);
        ull ans = a[0][0] - 1;

        ac.build();
        ans -= ac.cntIllegal(L);
        printf("%llu\n", ans);
    }

    return 0;
}