用c语言写代码,要求给定字符串s和t,问s有多少个子序列等于t,输入形式例如”nooooder”,”nowcoder” 输出为2
时间: 2024-02-12 09:05:49 浏览: 25
好的,让我来解答你的问题。这是一个比较经典的字符串匹配问题,可以使用动态规划来解决。具体来说,可以使用一个二维数组dp[i][j]表示字符串s前i个字符和字符串t前j个字符匹配的方案数。其中,dp[0][0]=1,表示两个空字符串匹配的方案数为1,其他情况下,如果s[i]==t[j],则有dp[i][j]=dp[i-1][j-1]+dp[i-1][j],表示当前字符匹配或不匹配两种情况下的方案数之和,如果不相等,则有dp[i][j]=dp[i-1][j],表示当前字符不能匹配,只能继承之前的方案数。最终,答案为dp[len_s][len_t],其中len_s和len_t分别表示字符串s和t的长度。下面是C语言的代码实现:
```
#include <stdio.h>
#include <string.h>
int numDistinct(char * s, char * t){
int len_s = strlen(s), len_t = strlen(t);
int dp[len_s+1][len_t+1];
memset(dp, 0, sizeof(dp));
for(int i=0; i<=len_s; i++) dp[i][0] = 1;
for(int i=1; i<=len_s; i++) {
for(int j=1; j<=len_t; j++) {
if(s[i-1]==t[j-1]) dp[i][j] = dp[i-1][j-1]+dp[i-1][j];
else dp[i][j] = dp[i-1][j];
}
}
return dp[len_s][len_t];
}
int main() {
char s[] = "nooooder";
char t[] = "nowcoder";
int ans = numDistinct(s, t);
printf("%d\n", ans);
return 0;
}
```
输出结果为2,符合题目要求。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)