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
| #include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define pct(x) __builtin_popcount(x)
using LL = long long;
const LL INF = 1e18;
const int T = 1000 + 100, S = 4e5 + 100, A = 14;
int n, cnt;
std::pair<int, LL> trans[A + 5][T];
char s[S];
LL d[(1 << A) + 100][T], ans = -INF;
bool vis[(1 << A) + 100][T];
struct ACAM
{
int ch[T][A + 5], fail[T], tot;
LL ed[T];
void ins(char *s, int v)
{
int p = 0;
for (int c; *s; ++s)
{
c = *s - 'a';
if (!ch[p][c]) ch[p][c] = ++tot;
p = ch[p][c];
}
ed[p] += v;
}
void bd()
{
std::queue<int> q;
fail[0] = 0;
for (int i = 0; i < A; ++i) if (ch[0][i]) fail[ch[0][i]] = 0, q.push(ch[0][i]);
while (!q.empty())
{
int x = q.front(); q.pop();
for (int i = 0, t; i < A; ++i)
if (t = ch[x][i])
{
fail[t] = ch[fail[x]][i], q.push(t);
ed[t] += ed[fail[t]];
}
else ch[x][i] = ch[fail[x]][i];
}
}
std::pair<int, LL> walk(int p, int pos)
{
LL res = 0;
while (s[pos] && s[pos] != '?')
{
p = ch[p][s[pos++] - 'a'];
res += ed[p];
}
return {p, res};
}
} ac;
void upd(int used, int x, LL v){ d[used][x] = std::max(v, d[used][x]), vis[used][x] = true; }
int main()
{
{
int num, c;
char t[T];
scanf("%d", &num);
for (int i = 1; i <= num; ++i) scanf("%s %d", t + 1, &c), ac.ins(t + 1, c);
ac.bd();
}
scanf("%s", s + 1), n = strlen(s + 1);
for (int i = 1; i <= n; ++i) if (s[i] == '?')
{
++cnt;
for (int j = ac.tot; ~j; --j) trans[cnt][j] = ac.walk(j, i + 1);
}
for (int i = (1 << A) - 1; ~i; --i)
for (int j = ac.tot; ~j; --j) d[i][j] = -INF, vis[i][j] = false;
auto t = ac.walk(0, 1); upd(0, t.fi, t.se);
for (int i = 0, p; i < (1 << A); ++i) if (pct(i) < cnt)
for (int j = ac.tot; ~j; --j) if (vis[i][j])
{
LL td = d[i][j];
for (int k = 0; k < A; ++k) if (!((i >> k) & 1))
{
p = ac.ch[j][k];
t = trans[pct(i) + 1][p];
upd(i | (1 << k), t.fi, td + t.se + ac.ed[p]);
}
}
for (int i = (1 << A) - 1; ~i; --i) if (pct(i) == cnt)
for (int j = ac.tot; ~j; --j) ans = std::max(ans, d[i][j]);
printf("%lld\n", ans);
return 0;
}
|