统计目标字符串在母串的子序列中出现的次数用c++实现
时间: 2023-11-14 09:07:16 浏览: 43
以下是统计目标字符串在母串的子序列中出现的次数的 C 代码实现:
```c
#include <stdio.h>
#include <string.h>
int countSubsequence(char* str, char* target) {
int n = strlen(str);
int m = strlen(target);
int dp[m+1][n+1];
memset(dp, 0, sizeof(dp));
for (int j = 0; j <= n; j++) {
dp[0][j] = 1;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (target[i-1] == str[j-1]) {
dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
} else {
dp[i][j] = dp[i][j-1];
}
}
}
return dp[m][n];
}
int main() {
char str[] = "abcbcabc";
char target[] = "abc";
int res = countSubsequence(str, target);
printf("The target string '%s' appears %d times in the mother string '%s'\n", target, res, str);
return 0;
}
```
代码中采用动态规划的思想实现了统计目标字符串在母串的子序列中出现的次数。其中 `dp[i][j]` 表示目标字符串的前 `i` 个字符在母串的前 `j` 个字符中出现的次数,转移方程为:
- 当 `target[i-1] == str[j-1]` 时,目标字符串的第 `i` 个字符与母串的第 `j` 个字符匹配,此时 `dp[i][j] = dp[i-1][j-1] + dp[i][j-1]`,前者表示目标字符串的前 `i-1` 个字符在母串的前 `j-1` 个字符中出现的次数,后者表示目标字符串的前 `i` 个字符在母串的前 `j-1` 个字符中出现的次数。
- 当 `target[i-1] != str[j-1]` 时,目标字符串的第 `i` 个字符与母串的第 `j` 个字符不匹配,此时 `dp[i][j] = dp[i][j-1]`,表示目标字符串的前 `i` 个字符在母串的前 `j-1` 个字符中出现的次数。
最终结果为 `dp[m][n]`,其中 `m` 和 `n` 分别为目标字符串和母串的长度。