Obsessive String

题意

给你两个串 s, t：问满足以下的条件的划分方案数：
1、S 是 s 的一个不重叠的划分 (不要求覆盖)
2、对 S 中的串 x，t 是 x 的子串

其中 $1\le len(s), len(t)\le10^5$，请输出方案数模 1e9 + 7 的结果

思路

这很明显是一道 dp 求方案数的题目，不妨设 $dp[i]$ 代表仅考虑前 $i$ 个字母，方案的个数。

$dp[i]$ 可以从 $dp[i-1]$ 中转移过来，也就是 $dp[i] += dp[i - 1]$

如果前 $i$ 个字母都不存在 $t$ 的子串，那么 $dp[i] = 0$

如果存在 $t$ 的子串，$s[i] = x + t + y$，其中 $x$ 和 $y$ 都可以是空串，而且 $t$ 不是 $y$ 的子串，因此划分方案也可以这样转移：

${前 len(x) 个划分方案，x[len(x): ] + t + y}$

${前 len(x) - 1 个划分方案，x[len(x) - 1: ] + t + y}$

${前 len(x) - 2 个划分方案，x[len(x) - 2: ] + t + y}$

…

${前 0 个划分方案，x[0: ] + t + y}$

因此 $dp[i] += \sum \limits_{i=0}^{len(x)}dp[i] + len(x) + 1$

维护每个前 $i$ 个字母中 $x$ 的长度即可，求和部分可以前缀和优化。

代码

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7, N = 1e5 + 5;
char s[N], t[N];
int nxt[N], pre[N], dp[N], sum[N];

int main() {
    scanf("%s %s", s + 1, t + 1);

    int n = strlen(s + 1), m = strlen(t + 1);

    for (int i = 1, j = 0; t[i] ; nxt[++i] = ++j)
        while (j != 0 && t[i] != t[j]) j = nxt[j];

    for (int i = 1, j = 1; s[i]; ++i) {
        while (j != 0 && s[i] != t[j]) j = nxt[j];
        j = j + 1;
        if (!t[j]) pre[i] = i - m + 1, j = nxt[j];
    }

    for (int i = 1; i <= n; ++i) {
        if (!pre[i]) pre[i] = pre[i - 1];
        dp[i] = (dp[i] + dp[i - 1]) % MOD;
        if (pre[i]) dp[i] = (dp[i] + sum[pre[i] - 1] + pre[i]) % MOD;
        sum[i] = (sum[i - 1] + dp[i]) % MOD;
    }

    printf("%d\n", dp[n]);
    return 0;
}