hyz's blog
0%

kuangbin带你飞 专题十七 AC自动机 题解

发表于

kuangin带你飞专题十七 AC自动机 传送门
AC自动机是著名的多模匹配算法，在ACM中通常会结合计数问题、动态规划问题等一起出现。

A. HDU 2222 Keywords Search

统计字符串出现的个数，AC自动机模板题。

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
#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=5e5+9;
const int shift=1e3+9;
const double Eps=1e-7;


/********************************************************************************/
/* AC自动机：解决多个模式串匹配问题(Untested)
 */
struct AC {
    int next[N][26], fail[N], end[N], idx, root;
    void init() {
        idx = 0;
        root = newNode();
    }
    int newNode() {
        for(int i = 0; i < 26; i++)
            next[idx][i] = -1;
        end[idx] = 0;
        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]++;
    }
    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();
            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]);
                }
            }
        }
    }
    int query(char s[]) {
        int ans = 0, len = strlen(s), now = root;
        for(int i = 0; i < len; i++) {
            now = next[now][s[i] - 'a'];
            int temp = now;
            while(temp != root) {
                ans += end[temp];
                end[temp] = 0;
                temp = fail[temp];
            }
        }
        return ans;
    }
    void debug() {
        printf("%37c", ' ');
        for(int i = 0; i < 26; i++)
            printf("%2c", i + 'a');
        printf("\n");
        for(int i = 0;i < idx;i++) {
            printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]);
            for(int j = 0;j < 26;j++)
                printf("%2d",next[i][j]);
            printf("]\n");
        }
    }
}ac;
/********************************************************************************/

int T, n;
char s[N * 2];

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        ac.init();
        for(int i = 0; i < n; i++) {
            scanf("%s", s);
            ac.insert(s);
        }
        ac.build();
        scanf("%s", s);
        int ans = ac.query(s);
        printf("%d\n", ans);
    }

    return 0;
}

B.HDU 2896 病毒侵袭

和上道题差不多，但这道题要求输出出现的字符串，修改一下节点保存的信息即可。

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
// 模式串之间可以重叠

#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=1e5+9;
const int shift=1e3+9;
const double Eps=1e-7;

int n, total;
char s[10009];
//写AC自动机等树状数据结构一定要注意空间！
//比如这道题，多申请个set<int> se[N] 就会MLE 
struct acAuto {
    int next[N][128], fail[N], root, L;
    vi end[N];
    void init() {
        L = 0;
        root = newNode();
    }
    int newNode() {
        for(int i = 0; i < 128; i++)
            next[L][i] = -1;
        end[L].clear();
        return L++;
    }
    void insert(char s[], int id) {
        int now = root, len = strlen(s);
        for(int i = 0; i < len; i++) {
            if(next[now][s[i]] == -1)
                next[now][s[i]] = newNode();
            now = next[now][s[i]];
        }
        end[now].push_back(id);
    }
    void build() {
        queue<int> que;
        fail[root] = root;	//!
        for(int i = 0; i < 128; 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();
            for(int i = 0; i < 128; 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]);
                }
            }
        }
    }
    bool query(char s[], int id) {
        int now = root, len = strlen(s);
        set<int> se;
        bool flag[N];
        memset(flag, 0, sizeof flag);
        for(int i = 0; i < len; i++) {
            now = next[now][s[i]];
            int temp = now;
            while(temp != root) {
                if(!flag[temp]) {
                    for(auto j: end[temp])
                        se.insert(j);
                    flag[temp] = true;
                }
                if(se.size() >= 3) break;
                temp = fail[temp];
            }
        }
        if(se.size()) {
            printf("web %d:", id);
            for(auto i: se)
                printf(" %d", i);
            printf("\n");
            return true;
        }
        return false;
    }
    void debug() {
        printf("%27c", ' ');
        for(int i = 0; i < 26; i++)
            printf("%2c", i + 'a');
        printf("\n");
        for(int i = 0;i < L;i++) {
            printf("id = %3d,fail = %3d,chi = [",i,fail[i]);
            for(int j = 0;j < 26;j++)
                printf("%2d",next[i][j]);
            printf("]\n");
        }
    }
}ac;

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    scanf("%d", &n);
    ac.init();
    for(int i = 1; i <= n; i++) {
        scanf("%s", s);
        ac.insert(s, i);
    }
    ac.build();
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%s", s);
        if(ac.query(s ,i))
            total++;
    }
    printf("total: %d\n", total);

    return 0;
}

C. HDU 3065 病毒侵袭持续中

需要统计各字符串出现的次数，使用vector来维护节点上出现的字符串即可。
注意是多组样例，初始化要处理好。

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
//题目有点坑啊，没有说多组样例，WA了一发:(

#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=1e5+9;
const int shift=1e3+9;
const double Eps=1e-7;

int n;
char s[2000009];
char ss[1009][59];

struct acAuto {
    int next[N][26], fail[N], root, L;
    vi end[N];
    void init() {
        L = 0;
        root = newNode();
    }
    int newNode() {
        for(int i = 0; i < 26; i++)
            next[L][i] = -1;
        end[L].clear();
        return L++;
    }
    void insert(char s[], int id) {
        int now = root, len = strlen(s);
        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].push_back(id);
    }
    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();
            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]);
                }
            }
        }
    }
    void query(char s[]) {
        int now = root, len = strlen(s);
        int cnt[N];
        bool flag[N];
        memset(flag, 0, sizeof flag);
        memset(cnt, 0, sizeof cnt);
        set<int>se;
        for(int i = 0; i < len; i++) {
            now = isupper(s[i]) ? next[now][s[i] - 'A'] : root;
            int temp = now;
            while(temp != root) {
                for(auto id: end[temp]) {
                    cnt[id]++;
                    if(!flag[id]) {
                        se.insert(id);
                        flag[id] = true;
                    }
                }
                temp = fail[temp];
            }
        }
        for(auto i: se) {
            printf("%s: %d\n", ss[i], cnt[i]);
        }
    }
}ac;


int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(~scanf("%d", &n)) {
        ac.init();
        for(int i = 1; i <= n; i++) {
            scanf("%s", ss[i]);
            ac.insert(ss[i], i);
        }
        ac.build();
        scanf("%s", s);
        ac.query(s);
    }

    return 0;
}

D. ZOJ 3430 Detect the Virus

题目有点难懂，留坑待填。

E. POJ 2778 DNA Sequence

求不含模式串的字符串总数。
该计数问题可用AC自动机+矩阵快速幂解决，很经典。
详细题解传送门

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
147
148
149
150
151
152
153
154
#pragma comment(linker, "/STACK:102400000,102400000")    //手动扩栈

#include<set>
#include<map>
#include<ctime>        //CLOCKS_PER_SEC;clock_t t=clock();
#include<cmath>        
#include<queue>
#include<bitset>
#include<cctype>
#include<cstdio>
#include<vector>
#include<string>    //getline(cin, line);
#include<sstream>    //stringstream ss(line);(ss is a stream like cin).
#include<cstdlib>
#include<cstring> 
#include<cfloat>    //X=FLT,DBL,LDBL;X_MANT_DIG,X_DIG,X_MIN_10_EXP,X_MIN_10_EXP,X_MIN,X_MAX,X_EPSILON
#include<climits>    //INT_MAX,LLONG_MAX
#include<iostream>     //ios_base::sync_with_stdio(false);
#include<algorithm>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=1e5+9;
const int shift=1e3+9;
const double Eps=1e-7;

const int mod =    100000;
map<char, int> m;
int n, mm;
char s[19];


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

typedef vector<vi> mat;

mat mul(mat A, mat B){
    mat C(A.size(), vi(B[0].size()));
    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]=(1LL * C[i][j]+1LL * A[i][k]*B[k][j])%mod;
    return C;
}

mat pow(mat A, int n){
    mat B(A.size(), vi(A.size()));
    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;
}

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

struct acAuto {
    int next[109][4], fail[109], L, root;
    bool end[109];
    void init() {
        L = 0;
        m['A'] = 0;
        m['T'] = 1;
        m['C'] = 2;
        m['G'] = 3;
        root = newNode();
    }
    int newNode() {
        for(int i = 0; i < 4; i++)
            next[L][i] = -1;
        end[L] = false;
        return L++;
    }
    void insert(char s[]) {
        int len = strlen(s), now = root;
        for(int i = 0; i < len; i++) {
            int j = m[s[i]];
            if(next[now][j] == -1)
                next[now][j] = newNode();
            now = next[now][j];
        }
        end[now] = true;
    }
    void build() {
        fail[root] = root;
        queue<int> que;
        for(int i = 0; i < 4; 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]])	//假如fail转移到的状态不合法，那么该状态也不合法！
                end[now] = true;
            for(int i = 0; i < 4; 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]);
                }
            }
        }
    }
    void buildMatrix(::mat &a) {
        for(int i = 0; i < L; i++)
            for(int j = 0; j < 4; j++)
                if(end[next[i][j]] == false)
                    a[i][next[i][j]]++;
    }
    void solve() {
        ::mat a(L, vi(L));
        buildMatrix(a);
        a = pow(a, n);
        ll ans = 0;
        for(int j = 0; j < L; j++)
            (ans += a[0][j]) %= mod;
        printf("%lld\n", ans);
    }
}ac;

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(~scanf("%d%d", &mm, &n)) {
        ac.init();
        for(int i = 0; i < mm; i++) {
            scanf("%s", s);
            ac.insert(s);
        }
        ac.build();
        ac.solve();
    };
    return 0;
}

F. HDU 2243 考研路茫茫――单词情结

求含模式串的字符串总数，注意这道题的字符串长度是可变的，所以矩阵构造需要有所变化。
同样是计数问题，还是AC自动机+矩阵快速幂的套路。
详细题解传送门

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;
}

G. POJ 1625 Censored!

求不含模式串的字符串总数，需要使用大数，但是不能使用矩阵快速幂，因为会MLE。
注意到m挺小，所以考虑用DP解决，而且还需要用滚动数组优化一下。

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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
#pragma comment(linker, "/STACK:102400000,102400000")    //手动扩栈

#include<set>
#include<map>
#include<ctime>        //CLOCKS_PER_SEC;clock_t t=clock();
#include<cmath>        
#include<queue>
#include<bitset>
#include<cctype>
#include<cstdio>
#include<vector>
#include<string>    //getline(cin, line);
#include<sstream>    //stringstream ss(line);(ss is a stream like cin).
#include<cstdlib>
#include<cstring>
#include<cfloat>    //X=FLT,DBL,LDBL;X_MANT_DIG,X_DIG,X_MIN_10_EXP,X_MIN_10_EXP,X_MIN,X_MAX,X_EPSILON
#include<climits>    //INT_MAX,LLONG_MAX
#include<iostream>     //ios_base::sync_with_stdio(false);
#include<algorithm>
#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;

int chr = 0;
char c, s[59];
map<char, int> m;
int n, mm, p;

/*
 * 高精度，支持乘法和加法(Tested 0 times)
 */
struct BigInt{
    const static int mod = 10000;
    const static int DLEN = 4;
    int a[90],len;
    BigInt(){
        memset(a,0,sizeof(a));
        len = 1;
    }
    BigInt(int v){
        memset(a,0,sizeof(a));
        len = 0;
        do{
            a[len++] = v%mod;
            v /= mod;
        }while(v);
    }
    BigInt(const char s[]){
        memset(a,0,sizeof(a));
        int L = strlen(s);
        len = L/DLEN;
        if(L%DLEN)len++;
        int index = 0;
        for(int i = L-1;i >= 0;i -= DLEN){
            int t = 0;
            int k = i - DLEN + 1;
            if(k < 0)k = 0;
            for(int j = k;j <= i;j++)
                t = t*10 + s[j] - '0';
            a[index++] = t;
        }
    }
    BigInt operator +(const BigInt &b)const{
        BigInt res;
        res.len = max(len,b.len);
        for(int i = 0;i <= res.len;i++)
            res.a[i] = 0;
        for(int i = 0;i < res.len;i++){
            res.a[i] += ((i < len)?a[i]:0)+((i < b.len)?b.a[i]:0);
            res.a[i+1] += res.a[i]/mod;
            res.a[i] %= mod;
        }
        if(res.a[res.len] > 0)res.len++;
        return res;
    }
    BigInt operator *(const BigInt &b)const{
        BigInt res;
        for(int i = 0; i < len;i++){
            int up = 0;
            for(int j = 0;j < b.len;j++){
                int temp = a[i]*b.a[j] + res.a[i+j] + up;
                res.a[i+j] = temp%mod;
                up = temp/mod;
            }
            if(up != 0)
                res.a[i + b.len] = up;
        }
        res.len = len + b.len; while(res.a[res.len - 1] == 0 &&res.len > 1)res.len--;
        return res;
    }
    void output(){
        printf("%d",a[len-1]);
        for(int i = len-2;i >=0 ;i--)
            printf("%04d",a[i]);
        printf("\n");
    }
};

/* 矩阵快速幂：根据递推式快速计算第n项(Tested 1 times)
 * 矩阵构造、时间复杂度参考白书P201
 */
typedef vector<BigInt> vll;
typedef vector<vll> mat;

mat mul(mat A, mat B) {
    mat C(A.size(), vll(B[0].size(), 0));	// 假如为long long，vi需要修改为vll
    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));		// 假如为long long，vi需要修改为vll
    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 3 times)
 */
struct AC {
    int next[109][50], fail[109], end[109], idx, root;
    void init() {
        idx = 0;
        root = newNode();
    }
    int newNode() {
        for(int i = 0; i < chr; 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++) {
            int c = m[s[i]];
            if(next[now][c] == -1)
                next[now][c] = newNode();
            now = next[now][c];
        }
        end[now] = true;	//根据实际情况可能需要保存不同的信息
    }
    void build() {
        queue<int> que;
        fail[root] = root;
        for(int i = 0; i < chr; 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 < chr; 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]);
                }
            }
        }
    }
    void query() {
        mat a(idx, vll(idx, 0));
        for(int i = 0; i < idx; i++)
            for(int j = 0; j < chr; j++)
                if(end[next[i][j]] == false)
                    a[i][next[i][j]] = a[i][next[i][j]] + 1;
        mat dp(2, vll(idx, 0));
        dp[0][0] = 1;
        int now = 0;
        for(int i = 0; i < mm; i++) {
            now ^= 1;
            for(int j = 0; j < idx; j++)
                dp[now][j] = 0;
            for(int j = 0; j < idx; j++)
                for(int k = 0; k < idx; k++)
                    dp[now][k] = dp[now][k] + dp[now ^ 1][j] * a[j][k];
        }
        BigInt ans = 0;
        for(int i = 0; i < idx; i++)
            ans = ans + dp[now][i];
        ans.output();
    }
    void debug() {
        printf("%37c", ' ');
        for(int i = 0; i < 26; i++)
            printf("%2c", i + 'a');
        printf("\n");
        for(int i = 0;i < idx;i++) {
            printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]);
            for(int j = 0;j < 26;j++)
                printf("%2d",next[i][j]);
            printf("]\n");
        }
    }
}ac;

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(~scanf("%d%d%d", &n, &mm, &p)) {
        chr = 0;
        getchar();
        m.clear();
        for(int i = 0; i < n; i++) {
            c = getchar();
            m[c] = chr++;
        }
        ac.init();
        while(p--) {
            scanf("%s", s);
            ac.insert(s);
        }
        ac.build();
        ac.query();
    }

    return 0;
}

H. HDU 2825 Wireless Password

AC自动机+动态规划
详细题解传送门

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
147
148
149
150
151
#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;

const int mod = 20090717;

char s[19];
int n, m, k, dp[26][109][1029];

struct node {
    int idx, status;
    node() {}
    node(int idx, int status): idx(idx), status(status){}
};

/********************************************************************************/
/* AC自动机：解决多个模式串匹配问题(Tested 3 times)
 */
struct AC {
    int next[109][26], fail[109], end[109], idx, root; // 可以修改下数组大小，以防MLE
    void init() {
        idx = 0;
        root = newNode();
    }
    int newNode() {
        for(int i = 0; i < 26; i++)
            next[idx][i] = -1;
        end[idx] = 0;
        return idx++;
    }
    void insert(char s[], int id) {
        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] = 1 << id;
    }
    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();
            end[now] |= end[fail[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];
                    que.push(next[now][i]);
                }
            }
        }
    }
    void query() {
        for(int i = 0; i <= n; i++)
            for(int j = 0; j < idx; j++)
                for(int k = 0; k < (1 << m); k++)
                    dp[i][j][k] = 0;
        dp[0][0][0] = 1;
        queue<node> que;
        que.push(node{0, 0});
        bool vis[259][1029];
        for(int i = 1; i <= n; i++) {
            queue<node> nextque;
            memset(vis, 0, sizeof vis);
            while(que.size()) {
                node t = que.front();
                que.pop();
                for(int o = 0; o < 26; o++) {
                    int j = t.idx;
                    int k = t.status;
                    int newj = next[j][o];
                    int newk = t.status | end[newj];
                    dp[i][newj][newk] += dp[i - 1][j][k];
                    if(dp[i][newj][newk] >= mod)
                        dp[i][newj][newk] -= mod;
                    if(!vis[newj][newk]) {
                        vis[newj][newk] = true;
                        nextque.push({newj, newk});
                    }
                }
            }
            que = nextque;
        }
        ll ans = 0;
        for(int i = 0; i < idx; i++) {
            for(int j = 0; j < 1 << m; j++) {
                // 可以把__builtin_popcount(j)预处理掉，这样更快
                if(__builtin_popcount(j) >= k) {
                    ans += dp[n][i][j];
                    if(ans >= mod)
                        ans -= mod;
                }
            }
        }
        printf("%lld\n", ans);
    }
    void debug() {
        printf("%37c", ' ');
        for(int i = 0; i < 26; i++)
            printf("%2c", i + 'a');
        printf("\n");
        for(int i = 0;i < idx;i++) {
            printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]);
            for(int j = 0;j < 26;j++)
                printf("%2d",next[i][j]);
            printf("]\n");
        }
    }
}ac;
/********************************************************************************/

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(~scanf("%d%d%d", &n, &m, &k) && n) {
        ac.init();
        for(int i = 0; i < m; i++) {
            scanf("%s", s);
            ac.insert(s, i);
        }
        ac.build();
        ac.query();
    }

    return 0;
}

I. HDU 2296 Ring

AC自动机+动态规划

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
147
148
149
150
151
152
153
154
#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 = 1e3+9;

string min(string s, string t) {
    if(s.length() < t.length())
        return s;
    return s < t ? s : t;
}

/* AC自动机：解决多个模式串匹配问题(Tested 4 times)
 */
struct AC {
    int next[N][26], fail[N], end[N], idx, root; // 可以修改下数组大小，以防MLE
    string c[N];
    int dp[59][N];
    string s[59][N];
    void init() {
        idx = 0;
        root = newNode("");
    }
    int newNode(string cc) {
        for(int i = 0; i < 26; i++)
            next[idx][i] = -1;
        end[idx] = 0;
        c[idx] = cc;
        return idx++;
    }
    void insert(char s[], int d) {
        int len = strlen(s), now = root;
        for(int i = 0; i < len; i++) {
            string t; t += s[i];
            if(next[now][s[i] - 'a'] == -1)
                next[now][s[i] - 'a'] = newNode(t);
            now = next[now][s[i] - 'a'];
        }
        end[now] += d;	//根据实际情况可能需要保存不同的信息
    }
    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();
            end[now] += end[fail[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];
                    que.push(next[now][i]);
                }
            }
        }
    }
    void query(int n) {
        string ans;
        int ma = -1;
        memset(dp, -1, sizeof dp);
        dp[0][0] = 0;
        for(int i = 1; i <= n; i++) {
            for(int u = 0; u < idx; u++) {
                if(dp[i-1][u] == -1) continue;
                for(int k = 0; k < 26; k++) {
                    int v = next[u][k];
                    if(dp[i-1][u] + end[v] > dp[i][v]) {
                        dp[i][v] = dp[i-1][u] + end[v];
                        s[i][v] = s[i-1][u] + c[v];
                    }
                    else if(dp[i-1][u] + end[v] == dp[i][v] && s[i-1][u] + c[u] < s[i][v]) {
                        s[i][v] = s[i-1][u] + c[v];
                    }
                }
            }
            for(int j = 0; j < idx; j++)
                ma = max(ma, dp[i][j]);
        }
        if(ma <= 0)
            cout << "" << endl;
        else {
            for(int i = 1; i <= n; i++) {
                bool flag = false;
                string ans = "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz";
                for(int j = 0; j < idx; j++) {
                    if(dp[i][j] == ma) {
                        ans = min(ans, s[i][j]);	//重载了min函数
                        flag = true;
                    }
                }
                if(flag) {
                    cout << ans << endl;
                    return;
                }
            }
        }
    }
    void debug() {
        printf("%37c", ' ');
        for(int i = 0; i < 26; i++)
            printf("%2c", i + 'a');
        printf("\n");
        for(int i = 0;i < idx;i++) {
            printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]);
            for(int j = 0;j < 26;j++)
                printf("%2d",next[i][j]);
            printf("]\n");
        }
    }
}ac;

int T, n, m, d;
char s[109][19];

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    cin >> T;
    while(T--) {
        scanf("%d%d", &n, &m);
        ac.init();
        for(int i = 0; i < m; i++) {
            scanf("%s", s[i]);
        }
        for(int i = 0; i < m; i++) {
            scanf("%d", &d);
            ac.insert(s[i], d);
        }
        ac.build();
        ac.query(n);
    }

    return 0;
}

J. HDU 2457 DNA repair

AC自动机+动态规划

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
#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 = 1e3+9;

int dp[1009][1009];
map<char, int> m;
int kase;

/********************************************************************************/
/* AC自动机：解决多个模式串匹配问题(Tested 5 times)
 */
struct AC {
    int next[N][4], fail[N], idx, root; // 可以修改下数组大小，以防MLE
    bool end[N];
    void init() {
        idx = 0;
        root = newNode();
    }
    int newNode() {
        for(int i = 0; i < 4; i++)
            next[idx][i] = -1;
        end[idx] = true;
        return idx++;
    }
    void insert(char s[]) {
        int len = strlen(s), now = root;
        for(int i = 0; i < len; i++) {
            if(next[now][m[s[i]]] == -1)
                next[now][m[s[i]]] = newNode();
            now = next[now][m[s[i]]];
        }
        end[now] = false;	//根据实际情况可能需要保存不同的信息
    }
    void build() {
        queue<int> que;
        fail[root] = root;
        for(int i = 0; i < 4; 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]]) end[now] = end[fail[now]];
            for(int i = 0; i < 4; 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]);
                }
            }
        }
    }
    void query(char s[]) {
        memset(dp, INF, sizeof dp);
        dp[0][0] = 0;
        int len = strlen(s);
        int ans = INF;
        for(int i = 0; i < len; i++) {
            bool flag = false;
            for(int u = 0; u < idx; u++) {
                if(dp[i][u] == INF) continue;
                int v = next[u][m[s[i]]];
                if(end[v]) {
                    flag = true;
                    dp[i+1][v] = min(dp[i+1][v], dp[i][u]);
                }
                for(int j = 0; j < 4; j++) {
                    if(j == m[s[i]]) continue;
                    v = next[u][j];
                    if(end[v]) {
                        dp[i+1][v] = min(dp[i+1][v], dp[i][u] + 1);
                        flag = true;
                    }
                }
            }
            if(!flag) {
                printf("Case %d: %d\n", ++kase, -1);
                return;
            }
        }
        for(int j = 0; j < idx; j++)
            ans = min(ans, dp[len][j]);
        printf("Case %d: %d\n", ++kase, ans);
    }
    void debug() {
        printf("%37c", ' ');
        for(int i = 0; i < 26; i++)
            printf("%2c", i + 'a');
        printf("\n");
        for(int i = 0;i < idx;i++) {
            printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]);
            for(int j = 0;j < 26;j++)
                printf("%2d",next[i][j]);
            printf("]\n");
        }
    }
}ac;
/********************************************************************************/

char s[1009];
int n;

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    m['A'] = 0; m['C'] = 1; m['G'] = 2; m['T'] = 3;
    while(~scanf("%d", &n) && n) {
        ac.init();
        for(int i = 0; i < n; i++) {
            scanf("%s", s);
            ac.insert(s);
        }
        ac.build();
        scanf("%s", s);
        ac.query(s);
    }

    return 0;
}

K. ZOJ 3228 Searching the String

AC自动机+计数

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
#pragma comment(linker, "/STACK:102400000,102400000")    //手动扩栈

#include<set>
#include<map>
#include<ctime>        //CLOCKS_PER_SEC;clock_t t=clock();
#include<cmath>        
#include<queue>
#include<bitset>
#include<cctype>
#include<cstdio>
#include<vector>
#include<string>    //getline(cin, line);
#include<sstream>    //stringstream ss(line);(ss is a stream like cin).
#include<cstdlib>
#include<cstring>
#include<cfloat>    //X=FLT,DBL,LDBL;X_MANT_DIG,X_DIG,X_MIN_10_EXP,X_MIN_10_EXP,X_MIN,X_MAX,X_EPSILON
#include<climits>    //INT_MAX,LLONG_MAX
#include<iostream>     //ios_base::sync_with_stdio(false);
#include<algorithm>
#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 = 6e5+9;

char s[N], t[9];
int n, ty[N], pos[N], cnt[N][2];    //改用pos记录位置，避免在ac自动机里面使用end集合，妙

/********************************************************************************/
/* AC自动机：解决多个模式串匹配问题(Tested 6 times)
 */
struct AC {
    int next[N][26], fail[N], deep[N], idx, root;
    void init() {
        idx = 0;
        root = newNode();
        deep[root] = 0;
    }
    int newNode() {
        for(int i = 0; i < 26; i++)
            next[idx][i] = -1;
        cnt[idx][0] = cnt[idx][1] = 0;
        return idx++;
    }
    int 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();
                deep[next[now][s[i] - 'a']] = i + 1;
            }
            now = next[now][s[i] - 'a'];
        }
        return now;
    }
    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();
            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]);
                }
            }
        }
    }
    void query(char s[]) {
        int len = strlen(s), now = root;
        int last[N];
        memset(last, -1, sizeof last);
        for(int i = 0; i < len; i++) {
            now = next[now][s[i] - 'a'];
            int temp = now;
            while(temp != root) {
                cnt[temp][0]++;
                if(i - last[temp] >= deep[temp]) {
                    cnt[temp][1]++;
                    last[temp] = i;
                }
                temp = fail[temp];
            }
        }
        for(int i = 0; i < n; i++)
            printf("%d\n", cnt[pos[i]][ty[i]]);
        puts("");
    }
    void debug() {
        printf("%37c", ' ');
        for(int i = 0; i < 26; i++)
            printf("%2c", i + 'a');
        printf("\n");
        for(int i = 0;i < idx;i++) {
            //printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]);
            for(int j = 0;j < 26;j++)
                printf("%2d",next[i][j]);
            printf("]\n");
        }
    }
}ac;
/********************************************************************************/


int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    int kase = 0;
    while(~scanf("%s", s)) {
        printf("Case %d\n", ++kase);
        scanf("%d", &n);
        ac.init();
        for(int i = 0; i < n; i++) {
            scanf("%d%s", &ty[i], t);
            pos[i] = ac.insert(t);
        }
        ac.build();
        ac.query(s);
    }

    return 0;
}

L. HDU 3341 Lost’s revenge

AC自动机+动态规划
为了不MLE，动态规划过程中的状态要巧妙设计下。

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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include<set>
#include<map>
#include<ctime>        //CLOCKS_PER_SEC;clock_t t=clock();
#include<cmath>        
#include<queue>
#include<bitset>
#include<cctype>
#include<cstdio>
#include<vector>
#include<string>    //getline(cin, line);
#include<sstream>    //stringstream ss(line);(ss is a stream like cin).
#include<cstdlib>
#include<cstring>
#include<cfloat>    //X=FLT,DBL,LDBL;X_MANT_DIG,X_DIG,X_MIN_10_EXP,X_MIN_10_EXP,X_MIN,X_MAX,X_EPSILON
#include<climits>    //INT_MAX,LLONG_MAX
#include<iostream>     //ios_base::sync_with_stdio(false);
#include<algorithm>
#define x first
#define y second
#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 = 509;

map<char, int> m;
int dp[509][11*11*11*11+9];

/********************************************************************************/
/* AC自动机：解决多个模式串匹配问题(Tested 7 times)
*/
struct AC {
    int next[N][26], fail[N], idx, root, end[N]; // 可以修改下数组大小，以防MLE
    void init() {
        idx = 0;
        root = newNode();
    }
    int newNode() {
        for(int i = 0; i < 4; i++)
            next[idx][i] = -1;
        end[idx] = 0;
        return idx++;
    }
    void insert(char s[]) {
        int len = strlen(s), now = root;
        for(int i = 0; i < len; i++) {
            if(next[now][m[s[i]]] == -1)
                next[now][m[s[i]]] = newNode();
            now = next[now][m[s[i]]];
        }
        end[now]++;	//根据实际情况可能需要保存不同的信息
    }
    void build() {
        queue<int> que;
        fail[root] = root;
        for(int i = 0; i < 4; 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();
            end[now] += end[fail[now]];
            for(int i = 0; i < 4; 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]);
                }
            }
        }
    }
    int bit[4];
    int func(int i, int j, int k, int l) {
        return i * bit[3] + j * bit[2] + k * bit[1] + l * bit[0];
    }
    void query(char s[]) {
        int cnt[4];
        int len = strlen(s);
        memset(cnt, 0, sizeof cnt);
        for(int i = 0; i < len; i++)
            cnt[m[s[i]]]++;
        bit[3] = (cnt[2] + 1) * (cnt[1] + 1) * (cnt[0] + 1);
        bit[2] = (cnt[1] + 1) * (cnt[0] + 1);
        bit[1] = cnt[0] + 1;
        bit[0] = 1;
        memset(dp, -1, sizeof dp);
        dp[0][0] = 0;
        for(int i = 0; i <= cnt[3]; i++) {
            for(int j = 0; j <= cnt[2]; j++) {
                for(int k = 0; k <= cnt[1]; k++) {
                    for(int l = 0; l <= cnt[0]; l++) {
                        for(int u = 0; u < idx; u++) {
                            if(dp[u][func(i, j, k, l)] < 0) continue;
                            for(int o = 0; o < 4; o++) {
                                int v = next[u][o];
                                if(o == 0 && l == cnt[0]) continue;
                                if(o == 1 && k == cnt[1]) continue;
                                if(o == 2 && j == cnt[2]) continue;
                                if(o == 3 && i == cnt[3]) continue;
                                int id = func(i, j, k, l);
                                dp[v][id + bit[o]] = max(dp[v][id + bit[o]], dp[u][id] + end[v]);
                            }
                        }
                    }
                }
            }
        }
        int ans = -1;
        for(int i = 0; i < idx; i++)
            ans = max(ans, dp[i][func(cnt[3], cnt[2], cnt[1], cnt[0])]);
        printf("%d\n", ans);
    }
    void debug() {
        printf("%37c", ' ');
        for(int i = 0; i < 26; i++)
            printf("%2c", i + 'a');
        printf("\n");
        for(int i = 0;i < idx;i++) {
            printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]);
            for(int j = 0;j < 26;j++)
                printf("%2d",next[i][j]);
            printf("]\n");
        }
    }
}ac;
/********************************************************************************/

char s[49];
int n, kase;

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    m['A'] = 0; m['C'] = 1; m['G'] = 2; m['T'] = 3;
    while(~scanf("%d", &n) && n) {
        printf("Case %d: ", ++kase);
        ac.init();
        while(n--) {
            scanf("%s", s);
            ac.insert(s);
        }
        scanf("%s", s);
        ac.build();
        ac.query(s);
    }

    return 0;
}

M. HDU 3247 Resource Archiver

留坑待填。

N. ZOJ 3494 BCD Code

留坑待填。

O. HDU 4758 Walk Through Squares

AC自动机+动态规划

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
#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;

const int mod = 1000000007;
map<char, int> m;

/********************************************************************************/
/* AC自动机：解决多个模式串匹配问题(Tested 8 times)
 */
struct AC {
    int next[N][26], fail[N], idx, root, end[N]; // 可以修改下数组大小，以防MLE
    void init() {
        idx = 0;
        root = newNode();
    }
    int newNode() {
        for(int i = 0; i < 2; i++)
            next[idx][i] = -1;
        end[idx] = 0;
        return idx++;
    }
    void insert(char s[], int id) {
        int len = strlen(s), now = root;
        for(int i = 0; i < len; i++) {
            if(next[now][m[s[i]]] == -1)
                next[now][m[s[i]]] = newNode();
            now = next[now][m[s[i]]];
        }
        end[now] |= id;	//根据实际情况可能需要保存不同的信息
    }
    void build() {
        queue<int> que;
        fail[root] = root;
        for(int i = 0; i < 2; 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();
            end[now] |= end[fail[now]];
            for(int i = 0; i < 2; 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]);
                }
            }
        }
    }
    int bit[2], dp[209][101 * 101 + 9][4];
    int get(int i, int j) {
        return bit[1] * i + bit[0] * j;
    }
    void query(int down, int right) {
        bit[1] = right + 1;
        bit[0] = 1;
        memset(dp, 0, sizeof dp);
        dp[0][0][0] = 1;
        for(int i = 0; i <= down; i++) {
            for(int j = 0; j <= right; j++) {
                for(int u = 0; u < idx; u++) {
                    for(int k = 0; k < 4; k++) {
                        if(dp[u][get(i, j)][k] == 0) continue;
                        for(int o = 0; o < 2; o++) {
                             int v = next[u][o];
                             if(i == down && o == 0) continue;
                             if(j == right && o == 1) continue;
                             (dp[v][get(i + (o == 0), j + (o == 1))][k | end[v]] += dp[u][get(i, j)][k]) %= mod;
                        }
                    }
                }
            }
        }
        int ans = 0;
        for(int i = 0; i < idx; i++) {
            (ans += dp[i][down * bit[1] + right][3]) %= mod;
        }
        printf("%d\n", ans);
    }
    void debug() {
        printf("%37c", ' ');
        for(int i = 0; i < 26; i++)
            printf("%2c", i + 'a');
        printf("\n");
        for(int i = 0;i < idx;i++) {
            printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]);
            for(int j = 0;j < 26;j++)
                printf("%2d",next[i][j]);
            printf("]\n");
        }
    }
}ac;
/********************************************************************************/

int T, n, mm;
char s[N];

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    scanf("%d", &T);
    m['D'] = 0;
    m['R'] = 1;
    while(T--) {
        scanf("%d%d", &mm, &n);
        ac.init();
        for(int i = 0; i < 2; i++) {
            scanf("%s", s);
            ac.insert(s, i + 1);
        }
        ac.build();
        ac.query(n, mm);
    }

    return 0;
}

P. HDU 4511 小明系列故事――女友的考验

AC自动机+动态规划

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
#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 = 9223372036854775807;
const double Eps = 1e-7;

const int N = 509;

int n, m, k, b[9];
pair<double, double> a[59];

/********************************************************************************/
/* AC自动机：解决多个模式串匹配问题(Tested 9 times)
*/
struct AC {
    int next[N][50], fail[N], idx, root;
    bool end[N]; // 可以修改下数组大小，以防MLE
    void init() {
        idx = 0;
        root = newNode();
    }
    int newNode() {
        for(int i = 0; i < n; i++)
            next[idx][i] = -1;
        end[idx] = 0;
        return idx++;
    }
    void insert(int b[], int k) {
        int now = root;
        for(int i = 0; i < k; i++) {
            b[i]--;
            if(next[now][b[i]] == -1)
                next[now][b[i]] = newNode();
            now = next[now][b[i]];
        }
        end[now] = 1;	//根据实际情况可能需要保存不同的信息
    }
    void build() {
        queue<int> que;
        fail[root] = root;
        for(int i = 0; i < n; 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();
            end[now] |= end[fail[now]];
            for(int i = 0; i < n; 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]);
                }
            }
        }
    }
    inline double get(pair<double, double> a, pair<double, double> b) {
        return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
    }
    void query(int n) {
        double dp[50][509];
        for(int i = 0; i < n; i++)
            for(int j = 0; j < idx; j++)
                dp[i][j] = LINF;
        dp[0][next[root][0]] = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < idx; j++) {
                if(dp[i][j] >= LINF - Eps) continue;
                for(int k = i + 1; k < n; k++) {
                    int v = next[j][k];
                    if(end[v]) continue;
                    dp[k][v] = min(dp[k][v], dp[i][j] + get(a[i], a[k]));
                }
            }
        }
        double ans = LINF;
        for(int i = 0; i < idx; i++)
            ans = min(ans, dp[n-1][i]);
        if(ans >= LINF - Eps)
            printf("Can not be reached!\n");
        else
            printf("%.2f\n", ans);
    }
    void debug() {
        printf("%37c", ' ');
        for(int i = 0; i < 26; i++)
            printf("%2c", i + 'a');
        printf("\n");
        for(int i = 0;i < idx;i++) {
            printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]);
            for(int j = 0;j < 26;j++)
                printf("%2d",next[i][j]);
            printf("]\n");
        }
    }
}ac;
/********************************************************************************/

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(~scanf("%d%d", &n, &m) && n) {
        ac.init();
        for(int i = 0; i < n; i++)
            scanf("%lf%lf", &a[i].x, &a[i].y);
        for(int i = 0; i < m; i++) {
            scanf("%d", &k);
            for(int j = 0; j < k; j++)
                scanf("%d", b + j);
            ac.insert(b, k);
        }
        ac.build();
        ac.query(n);
    }

    return 0;
}