P3082 [USACO13MAR]Necklace G

1. Kmp上Dp（会T）

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
#include<iostream>
#include<cstring>
#include<algorithm>
using std::ios;
using std::cin;
using std::cout;
using std::min;
const int MAXlwrd = 1e3;
const int MAXltxt = 1e4;
const int INF = 0x3f3f3f3f;

char txt[MAXltxt + 10], wrd[MAXlwrd + 10]; int ltxt, lwrd;
int fail[MAXlwrd + 10];
int d[MAXltxt + 10][MAXlwrd + 10];
void EvaFail() {
    fail[1] = 0;
    int j = 0;
    for (int i = 2; i <= lwrd; ++i) {
        while (j && (wrd[j + 1] != wrd[i] || j == lwrd)) j = fail[j];
        if (wrd[j + 1] == wrd[i]) ++j;
        fail[i] = j;
    }
}
signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> (txt + 1) >> (wrd + 1);
    ltxt = strlen(txt + 1); lwrd = strlen(wrd + 1);
    EvaFail();
    memset(d, 0x3f, sizeof(d));
    d[0][0] = 0;
    for (int i = 0; i < ltxt; ++i) {
        for (int j = 0; j < lwrd; ++j) {
            int k = j;
            while (k && (wrd[k + 1] != txt[i + 1] || k == lwrd)) k = fail[k];
            if (wrd[k + 1] == txt[i + 1]) ++k;
            d[i + 1][k] = min(d[i + 1][k], d[i][j]);
            d[i + 1][j] = min(d[i + 1][j], d[i][j] + 1);
        }
    }
    int ans = INF;
    for (int i = 0; i < lwrd; ++i) {
        ans = min(ans, d[ltxt][i]);
    }
    cout << ans << '\n';
}

2. Ac自动机上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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using std::ios;
using std::cin;
using std::cout;
using std::queue;
using std::min;
const int MAXlwrd = 1e3;
const int MAXltxt = 1e4;
const int MAXnd = 1e3;
const int INF = 0x3f3f3f3f;

int cntnd, son[MAXnd + 10][26], fail[MAXnd + 10];
int Insert(char *str) {
    int len = strlen(str + 1);
    int cur = 0;
    for (int i = 1; i <= len; ++i) {
        if (!son[cur][str[i] - 'a']) {
            son[cur][str[i] - 'a'] = ++cntnd;
        }
        cur = son[cur][str[i] - 'a'];
    }
    return cur;
}
queue<int> q;
void EvaFail() {
    for (int i = 0; i < 26; ++i) {
        if (son[0][i]) {
            q.push(son[0][i]);
        }
    }
    while (!q.empty()) {
        int j = q.front(); q.pop();
        for (int i = 0; i < 26; ++i) {
            if (son[j][i]) {
                fail[son[j][i]] = son[fail[j]][i];
                q.push(son[j][i]);
            } else {
                son[j][i] = son[fail[j]][i];
            }
        }
    }
}

char wrd[MAXlwrd + 10], txt[MAXltxt + 10];
int n, lwrd, ltxt, d[MAXltxt + 10][MAXlwrd + 10];
signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> (txt + 1) >> (wrd + 1);
    ltxt = strlen(txt + 1); lwrd = strlen(wrd + 1);
    Insert(wrd);
    EvaFail();
    memset(d, 0x3f, sizeof(d));
    d[0][0] = 0;
    for (int i = 0; i < ltxt; ++i) {
        for (int j = 0; j < lwrd; ++j) {
            int k = j;
            k = son[k][txt[i + 1] - 'a'];
            d[i + 1][k] = min(d[i + 1][k], d[i][j]);
            d[i + 1][j] = min(d[i + 1][j], d[i][j] + 1);
        }
    }
    int ans = INF;
    for (int i = 0; i < lwrd; ++i) {
        ans = min(ans, d[ltxt][i]);
    }
    cout << ans << '\n';
}