Codeforces Round #820 (Div. 3) G-Cut Substrings（kmp状态机dp）

TP

题意：

• 给定两个字符串 s、t，问最少删除多少个 s 中出现的 t 串，使得 s 中不再存在任何 t 串。删除后的位置不拼接，而是变成 … 点

• 同时统计最少删除的方案数。

思路：

• 看到维护 最少 就可以联想到能不能用 dp 解决问题。但对于每一个 si 都要考虑前面是否删除过，导致当前匹配到 t 串的位置在哪，这显然就是一个 kmp状态机dp 问题。

• 对 t 串 kmp 处理，每个 ne 指针的位置都是一个状态。

• $dp[i][j]的含义为：s串匹配到前i个字符，对应匹配到t串j状态的最小删除数$

• $cnt[i][j]就是当前最小删除数维护的方案数$

分类讨论：

• 如果当前位置 $s_i$ 字母能使得 $j$ 状态转移成 $to$ 状态，$to$ 状态分为匹配到 m （即匹配了 t 整串），和 0 ~ m-1 状态。
• 匹配到 m ，整个 t 串要尝试删除。这里注意是直接判断 $s_{i-m+1,i}$ 是否与 t 串相同，而不是判断 to 状态是否为 m，对于每个原串中匹配的位置，都考虑删除的情况，转移。

abacaba
abaca
//如果判断 状态 == m，该样例结果是 1 2 ...
1
2
3

• i 由 i - m 所有可能的合法 0 ~ m-1 状态 中的最小删除数、对应方案数 转移过来。匹配后删除数 +1，位置都变成点，对应转移过去的状态应该是 0
  $dp[i+1][0]<=mi[i+1-m]+1$

• 匹配到 0 ~ m-1，那就直接 i 由 i - 1 转移，状态 j 到 to
  $dp[i+1][to]<=dp[i][j]$

• 类似最短路计数一样，维护最小删除数的同时维护方案数即可。注意清空。

$Code:$

#include
#include
#define debug cout << "debug---  "
#define debug_ cout << "\n---debug---\n"
#define oper(a) operator<(const a& ee)const
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define endl "\n"
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, int> PII;

const int N = 5e2 + 10, M = 2e6 + 10, mod = 1e9 + 7;
int INF = 0x3f3f3f3f; ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, B = 10, ki;

//kmp状态机，多状态dp
int ne[N];

int dp[N][N];//s 前 i 个字符，匹配到 j 状态 的 最小删除数
int mi[N], res[N];
int cnt[N][N];//最小删除数对应的方案数
char s[N], t[N];
bool st[N];

void solve() {
    cin >> s + 1;
    cin >> t + 1;
    n = strlen(s + 1);
    m = strlen(t + 1);

    mem(ne, 0);
    mem(st, 0);

    for (int i = 2, j = 0; i <= m; i++) {
        while (j && t[i] != t[j + 1])j = ne[j];
        if (t[i] == t[j + 1])j++;
        ne[i] = j;
    }

    //预处理每个位置终点 s 是否匹配 t
    for (int i = 1; i <= n; i++) {
        if (i >= m) {
            bool f = true;
            for (int j = i, len = m; j > i - m; j--, len--)
                if (t[len] != s[j])f = false;
            if (f)st[i] = true;
        }
    }

    mem(dp, 0x3f);
    mem(cnt, 0);
    dp[0][0] = 0;
    cnt[0][0] = 1;

    
    for (int i = 0; i < n; i++) {

        mi[i] = INF, res[i] = 0;
        for (int j = 0; j < m; j++) {
            if (dp[i][j] < mi[i]) {
                mi[i] = dp[i][j];
                res[i] = cnt[i][j];
            }
            else if (dp[i][j] == mi[i])
                res[i] = (res[i] + cnt[i][j]) % mod;
        }

        //匹配了 t 串、匹配到 m 的情况，由 i + 1 - m 的所有 不为 m 的 状态中维护的最小值、方案数转移过来
        //匹配后变成点，所以转移到状态 0
        if (st[i + 1]) {
            if (dp[i + 1][0] > mi[i + 1 - m] + 1) {
                dp[i + 1][0] = mi[i + 1 - m] + 1;
                cnt[i + 1][0] = res[i + 1 - m];
            }
            else if (dp[i + 1][0] == mi[i + 1 - m] + 1) {
                cnt[i + 1][0] = (cnt[i + 1][0] + res[i + 1 - m]) % mod;
            }
        }

        //由当前合法状态 [ i, j ] 推导到下一个字母 s[i + 1]
        for (int j = 0; j < m; j++) {

            int to = j;

            while (to && t[to + 1] != s[i + 1])to = ne[to];
            if (s[i + 1] == t[to + 1])to++;

            //匹配过去状态变成 to

            //只考虑不匹配到 m 的状态
            if (to != m) {
                if (dp[i + 1][to] > dp[i][j]) {
                    dp[i + 1][to] = dp[i][j];
                    cnt[i + 1][to] = cnt[i][j];
                }
                else if (dp[i + 1][to] == dp[i][j]) {
                    cnt[i + 1][to] = (cnt[i + 1][to] + cnt[i][j]) % mod;
                }
            }
        }
    }

    //维护最小和方案数
    int mi = INF, ans = 0;
    for (int j = 0; j < m; j++) {
        if (dp[n][j] < mi) {
            mi = dp[n][j];
            ans = cnt[n][j];
        }
        else if (dp[n][j] == mi)
            ans = (ans + cnt[n][j]) % mod;
    }
    
    cout << mi << ' ' << ans << endl;
}

signed main() {
    cinios;
    int T = 1;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        solve();
    }
    return 0;
}
/*
*/
//板子
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