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
|
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using ll = long long;
using ii = pair<int, int>;
int N, T, c[2552], f[2552], g[2552][26], G[2552][26];
ll out[2552], dp[2552][2552];
string B, S[2552];
int aho_corasick() {
memset(g, -1, sizeof g), memset(out, 0, sizeof out);
int nodes = 1;
for (int i = 0; i < N; i++) {
int cur = 0;
for (int j = 0; j < S[i].size(); j++) {
if (g[cur][S[i][j] - 'a'] == -1) g[cur][S[i][j] - 'a'] = ++nodes;
cur = g[cur][S[i][j] - 'a'];
}
++out[cur];
}
for (int ch = 0; ch < T; ch++) {
if (g[0][ch] == -1) g[0][ch] = 0;
}
memset(f, -1, sizeof f);
queue<int> q;
for (int ch = 0; ch < T; ch++) {
if (g[0][ch] != 0) {
f[g[0][ch]] = 0;
q.push(g[0][ch]);
}
}
while (!q.empty()) {
int state = q.front();
q.pop();
for (int ch = 0; ch < T; ch++) {
if (g[state][ch] == -1) continue;
int fail = f[state];
while (g[fail][ch] == -1) fail = f[fail];
f[g[state][ch]] = g[fail][ch];
out[g[state][ch]] += out[g[fail][ch]];
q.push(g[state][ch]);
}
}
return nodes;
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> N >> T;
for (int i = 0; i < N; ++i) cin >> S[i];
cin >> B;
int L = B.size();
for (int i = 0; i < L; ++i) cin >> c[i];
int M = aho_corasick();
for (int i = 0; i < M; ++i) {
for (int j = 0; j < T; ++j) {
int k = i;
while (g[k][j] == -1) k = f[k];
G[i][j] = g[k][j];
}
}
memset(dp, '?', sizeof dp);
dp[0][0] = 0;
for (int i = 0; i < L; ++i) {
for (int j = 0; j < M; ++j) {
if (!out[j]) {
for (int k = 0; k < T; ++k) {
dp[i + 1][G[j][k]] = min(dp[i][j] + c[i] * (k != B[i] - 'a'), dp[i + 1][G[j][k]]);
}
}
}
}
ll ans = 1e18;
for (int i = 0; i < M; ++i) {
if (!out[i]) ans = min(dp[L][i], ans);
}
cout << (ans < 1e18 ? ans : -1) << '\n';
}
|
