算法
(DP) $O(8n)$
我们可以先考虑以下简单的问题:
在字符串 abcababc
中有多少个 a
- 扫描每个字符,看在位置 $i$ 之前有多少个
a
,若位置 $i$ 处为a
,那么到 $i$ 为止的a
的数量就是在位置 $i$ 之前的a
的数量加一
在字符串 abcababc
中有多少个 ab
- 扫描每个字符,看在位置 $i$ 之前有多少个
ab
,若位置 $i$ 处为b
,那么到 $i$ 为止的ab
的数量就是在位置 $i$ 之前的ab
的数量与在位置 $i$ 之前的a
的数量之和
在字符串 abcababc
中有多少个 abc
- 扫描每个字符,看在位置 $i$ 之前有多少个
abc
,若位置 $i$ 处为c
,那么到 $i$ 为止的abc
的数量就是在位置 $i$ 之前的abc
的数量与在位置 $i$ 之前的ab
的数量之和
于是就很自然的引出了 dp
记 $T$ 为模式串,dp[i][j]
表示前 $i$ 个字符中可以组成 $T_1, T_1, \cdots, T_j$ 的数量
转移方程:
- 若 $S_i \neq T_j$,则 $dp[i][j] = dp[i - 1][j]$
- 若 $S_i = T_j$,则 $dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1]$
边界条件:
$dp[i][0] = 1$,表示空字符在主串中的数量是 $1$
C++ 代码
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::string;
using mint = modint1000000007;
int main() {
string s;
cin >> s;
int n = s.size();
vector dp(n + 1, vector<mint>(9));
rep(i, n + 1) dp[i][0] = 1;
string t = "chokudai";
rep(i, n)rep(j, 8) {
if (s[i] != t[j]) {
dp[i + 1][j + 1] = dp[i][j + 1];
}
else {
dp[i + 1][j + 1] = dp[i][j + 1] + dp[i][j];
}
}
cout << dp[n][8].val() << '\n';
return 0;
}
赞!困扰好久的状态转移,老铁一语点醒梦中人