CF494B Obsessive String (KMP,计数dp)

题目链接

洛谷

CF contest

CF problemset

题意简述

给你两个字符串 $S$ 和 $T$,你需要在 $S$ 中取若干个(至少一个)不相交的子串,使得每个子串都包含 $T$,求方案数模 $10^9+7$。

字符串长度小于等于 $10^5$。

简要做法

首先用某种字符串算法求出 $T$ 在 $S$ 中匹配的所有位置(一般人都会选择 KMP)。

记 $|S|=n$, $|T|=m$。

然后,我们记 $p_i$ 表示 $[i+m,n]$ 中最小的匹配位置(也就是 $S[i+1..n]$ 这个子串第一个匹配的位置),记 $q_i$ 表示 $[1,i]$ 中最大的匹配位置(也就是 $S[1..i]$ 这个子串最后一个匹配的位置)。

然后开始 dp,令 $f_i​$ 表示子串 $S[i+1..n]​$ 的答案。转移时,我们考虑选择下一个子串的右端点和左端点。右端点可以在 $[q_i,n]​$ 中选取,而对于一个右端点 $j​$,可以选择的左端点有 $p_j-m-i+1​$ 个。另外,也可以不继续选择下一个子串。所以可以得到转移方程:

$$f_i=1+\sum\limits_{j=q_i}^nf_j(p_j-m-i+1)$$

如果我们把 $g_i=\sum\limits_{j=i}^nf_jp_j$ 和 $h_i=\sum\limits_{j=i}^nf_j$ 分别存下来,就可以得到 $f_i=1+g_{q_i}-(m+i-1)f_{q_i}$,然后就可以 $\mathcal O(n)$ 计算了。

最后,这样计算的话会把一个子串都不选计入总数,所以答案要减一。

参考代码

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
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;

const int N = 100010;
const int mod = 1e9 + 7;

char s[N], t[N];
int n, m, nxt[N], q[N], p[N], f[N], g[N];

int main()
{
int i, k;

scanf("%s%s", s + 1, t + 1);
n = strlen(s + 1);
m = strlen(t + 1);

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

for (i = 1, k = 0; i <= n; ++i)
{
while (k && s[i] != t[k + 1]) k = nxt[k];
if (s[i] == t[k + 1]) ++k;
if (k == m) q[i - m] = p[i] = i;
}

for (i = 1; i <= n; ++i) if (!p[i]) p[i] = p[i - 1];

for (i = n; i >= 0; --i)
{
if (!q[i]) q[i] = q[i + 1];
if (q[i]) f[i] = (1 + g[q[i]] - (ll) f[q[i]] * (m + i - 1) % mod + mod) % mod;
else f[i] = 1;
g[i] = ((ll) f[i] * p[i] + g[i + 1]) % mod;
f[i] = (f[i] + f[i + 1]) % mod;
}

cout << (f[0] - f[1] + mod - 1) % mod;

return 0;
}