包含 KMP Trie AC自动机 dp/矩阵优化AC自动机
KMP:
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
|
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
char a[1000050],b[1000050];
int nxt[1000050];
int ()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s %s",a + 1,b + 1);
int len = strlen(a + 1);
memset(nxt,0,sizeof(nxt));
for(int i = 2;i <= len; ++ i)
{
int lst = nxt[i - 1];
while(a[lst + 1] != a[i] && lst) lst = nxt[lst];
if(a[lst + 1] == a[i]) lst ++;
nxt[i] = lst;
}
int cur = 0;
int ans = 0;
int len2 = strlen(b + 1);
for(int i = 1;i <= len2; ++ i)
{
while(b[i] != a[cur + 1] && cur)
cur = nxt[cur];
if(a[cur + 1] == b[i]) cur ++;
if(cur == len) ans ++;
}
cout<<ans<<endl;
}
}
|
Trie树
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
|
int son[5000050][10];
int val[5000050];
struct Trie
{
int cnt;
void init()
{
memset(son[0],0,sizeof(son[0]));
val[0] = 0;
cnt = 0;
}
void init_pos(int pos)
{
memset(son[pos],0,sizeof(son[pos]));
val[pos] = 0;
}
bool insert(char *s)
{
int cur = 0;
int len = strlen(s + 1);
int u;
for(int i = 1;i <= len; ++ i)
{
int u = son[cur][s[i] - '0'];
if(u == 0)
{
u = ++cnt;
init_pos(u);
son[cur][s[i] - '0'] = cnt;
cur = u;
}
else
{
if(val[u]) return false;
cur = u;
}
}
val[cur] ++;
return true;
}
bool work(int rt)
{
bool yn;
if(val[rt]) yn = true;
else yn = false;
for(int i = 0;i <= 9; ++ i)
{
int v = son[rt][i];
if(v != 0)
{
if(yn) return false;
else if(!work(v)) return false;
}
}
return true;
}
}Tr;
|
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
|
int son[3000050][26],val[3000050];
int cnt;
int fail[3000050];
int ans;
bool vis[3000050];
struct Trie_AC
{
int get_id(char c)
{
return c - 'a';
}
void init(int pos)
{
memset(son[pos],0,sizeof(son[pos]));
val[pos] = 0;
}
void insert(char *c,int num)
{
int len = strlen(c);
int u = 0;
for(int i = 0;i < len; ++ i)
{
int v = get_id(c[i]);
int tmp = u;
u = son[u][v];
if(u == 0)
{
init(++cnt);
son[tmp][v] = cnt;
u = cnt;
}
}
val[u]++;
}
void build()
{
queue<int> q;
fail[0] = 0;
for(int i = 0;i < 26; ++ i)
if(son[0][i])
{
q.push(son[0][i]);
fail[son[0][i]] = 0;
}
while(!q.empty())
{
int u = q.front();
q.pop();
for(int i = 0;i < 26; ++ i)
{
int f = fail[u];
if(!son[u][i]) continue;
while(f && !son[f][i]) f = fail[f];
fail[son[u][i]] = son[f][i];
q.push(son[u][i]);
}
}
}
void query(char *c)
{
int len = strlen(c);
int cur = 0;
for(int i = 0;i < len; ++ i)
{
int v = get_id(c[i]);
while(cur && !son[cur][v])
cur = fail[cur];
cur = son[cur][v];
int tmp = cur;
while(tmp)
{
ans += val[tmp];
val[tmp] = 0;
tmp = fail[tmp];
}
}
}
}Trie;
|
带dp的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
|
int son[2500][2];
int lst[205],fail[250];
int val[205];
int cnt;
int dp[101][101][202][4];
int n,m;
const int mod = 1000000007;
struct Trie
{
int get_id(char c)
{
return c == 'R';
}
void init(int pos)
{
son[pos][0] = son[pos][1] = 0;
val[pos] = 0;
}
void insert(char* c,int id)
{
int len = strlen(c);
int u = 0;
for(int i = 0;i < len; ++ i)
{
int v = son[u][get_id(c[i])];
if(!v)
{
son[u][get_id(c[i])] = ++cnt;
init(cnt);
u = cnt;
}
else
u = v;
}
val[u] |= id;
}
void Build()
{
queue <int> q;
lst[0] = fail[0] = 0;
for(int i = 0;i <= 1; ++ i)
{
int v = son[0][i];
if(v)
{
lst[v] = fail[v] = 0;
q.push(v);
}
}
while(!q.empty())
{
int u = q.front();q.pop();
val[u] |= val[lst[u]];
for(int i = 0;i < 2; ++ i)
{
int v = son[u][i];
if(!v)
{
son[u][i] = son[fail[u]][i];
continue;
}
int f = fail[u];
while(f && !son[f][i]) f = fail[f];
fail[v] = son[f][i];
lst[v] = val[fail[v]] ? fail[v] : lst[fail[v]];
q.push(v);
}
}
}
void Do_DP()
{
for(int i = 0;i <= n; ++ i)
for(int j = 0;j <= m; ++ j)
for(int k = 0;k <= cnt; ++ k)
for(int l = 0;l < 4; ++ l)
dp[i][j][k][l] = 0;
dp[0][0][0][0] = 1;
for(int i = 0;i <= n; ++ i)
for(int j = 0;j <= m; ++ j)
for(int k = 0;k <= cnt; ++ k)
for(int l = 0;l < 4; ++ l)
{
if(dp[i][j][k][l] == 0) continue;
if(i < n)
dp[i + 1][j][son[k][1]][l | val[son[k][1]]] += dp[i][j][k][l],dp[i + 1][j][son[k][1]][l | val[son[k][1]]] %= mod;
if(j < m)
dp[i][j + 1][son[k][0]][l | val[son[k][0]]] += dp[i][j][k][l],dp[i][j + 1][son[k][0]][l | val[son[k][0]]] %= mod;
}
long long qsum = 0;
for(int i = 0;i <= cnt; ++ i)
qsum += dp[n][m][i][3],qsum %= mod;
printf("%lldn",qsum);
}
}Trie;
|
带矩阵优化的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
|
long long son[2500][26];
long long lst[205],fail[250];
long long val[205];
long long cnt;
long long n,m;
const long long mod = 1000000007;
struct Matrix
{
unsigned long long sum[55][55];
long long sz;
void init(long long _sz)
{
sz = _sz;
for(long long i = 0;i <= sz; ++ i)
for(long long j = 0;j <= sz; ++ j)
sum[i][j] = 0;
}
Matrix operator * (const Matrix& a)
{
Matrix c;
c.init(a.sz);
long long lim = c.sz;
for(long long i = 0;i <= sz; ++ i)
for(long long j = 0;j <= sz; ++ j)
for(long long k = 0;k <= sz; ++ k)
c.sum[i][j] += a.sum[k][j] * sum[i][k];
return c;
}
};
Matrix qpow(Matrix A,long long tms)
{
if(tms == 1) return A;
else if(tms == 0)
{
Matrix E;
E.init(A.sz);
for(int i = 0;i <= A.sz; ++ i)
E.sum[i][i] = 1;
return E;
}
Matrix tmp = A;
tms -= 1;
while(tms)
{
if(tms & 1) tmp = tmp * A;
A = A * A;
tms >>= 1;
}
return tmp;
}
unsigned long long qpow(unsigned long long a,long long tms)
{
unsigned long long tmp = 1;
while(tms)
{
if(tms & 1) tmp *= a;
a *= a;
tms >>= 1;
}
return tmp;
}
struct Trie
{
long long get_id(char c)
{
return c - 'a';
}
void init(long long pos)
{
memset(son[pos],0,sizeof(son[pos]));
val[pos] = 0;
}
void insert(char* c,long long id)
{
long long len = strlen(c);
long long u = 0;
for(long long i = 0;i < len; ++ i)
{
long long v = son[u][get_id(c[i])];
if(!v)
{
son[u][get_id(c[i])] = ++cnt;
init(cnt);
u = cnt;
}
else
u = v;
}
val[u] |= id;
}
void Build()
{
queue <long long> q;
lst[0] = fail[0] = 0;
for(long long i = 0;i <= 25; ++ i)
{
long long v = son[0][i];
if(v)
{
lst[v] = fail[v] = 0;
q.push(v);
}
}
while(!q.empty())
{
long long u = q.front();q.pop();
val[u] |= val[lst[u]];
for(long long i = 0;i < 26; ++ i)
{
long long v = son[u][i];
if(!v)
{
son[u][i] = son[fail[u]][i];
continue;
}
long long f = fail[u];
while(f && !son[f][i]) f = fail[f];
fail[v] = son[f][i];
lst[v] = val[fail[v]] ? fail[v] : lst[fail[v]];
q.push(v);
}
}
}
void get_mat(Matrix& mat)
{
for(long long i = 0;i <= cnt; ++ i)
{
if(val[i]) continue;
for(long long j = 0;j < 26; ++ j)
{
long long k = son[i][j];
if(val[k]) continue;
mat.sum[i][k] ++;
}
}
for(long long i = 0;i <= cnt + 1; ++ i)
mat.sum[i][cnt] = 1;
}
}Trie;
|
近期评论