给你一个字符串S,S中只有小写英文字母,你需要计算S中含有多少个"helloworld"子序列,答案可能很大,请输出答案对998244353998244353取模之后的结果 某个序列的子序列是指从最初序列除去部分(可能0个)元素但不破坏余下元素的相对位置而形成的新序列。如"abcde","be","acd"是"abcde"的子序列,但"cbe"不是。
时间: 2023-03-25 17:04:53 浏览: 265
我可以回答这个问题。这是一个字符串计数问题,可以使用动态规划来解决。我们可以定义一个二维数组dp,其中dp[i][j]表示在S的前i个字符中,"helloworld"的前j个字符出现的次数。状态转移方程为:
如果S[i]等于"helloworld"的第j个字符,则dp[i][j] = dp[i-1][j-1] + dp[i-1][j],否则dp[i][j] = dp[i-1][j]。
最终答案为dp[n][10],其中n为S的长度。需要注意的是,由于答案可能很大,需要对998244353取模。
代码实现如下:
#include <iostream>
#include <cstring>
using namespace std;
const int MOD = 998244353;
const string target = "helloworld";
int main() {
string s;
cin >> s;
int n = s.length();
int dp[n+1][10];
memset(dp, , sizeof(dp));
for (int i = ; i <= n; i++) {
dp[i][] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 9; j++) {
if (s[i-1] == target[j-1]) {
dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % MOD;
} else {
dp[i][j] = dp[i-1][j];
}
}
}
cout << dp[n][9] << endl;
return ;
}
阅读全文