首页 > 其他 > 详细

子序列计数

时间:2020-04-09 17:27:34      阅读:123      评论:0      收藏:0      [点我收藏+]

Description
给你一个字符串,有它有多少个本质不同的子序列
Input
第一行给出字符串长度,小于等于100
第二行给出这个字符串

Output
如题
Sample Input
3
aab
Sample Output
6
//a,b,aa,ab,aab,还有一个空串

sol:

将next数组建好,然后统计树的大小

技术分享图片

代码如下:

 1 #include<bits/stdc++.h>
 2 #define rint register int
 3 #define deb(x) cerr<<#x<<" = "<<(x)<<‘\n‘;
 4 using namespace std;
 5 typedef long long ll;
 6 typedef pair <int,int> pii;
 7 const ll mod = 1e9 + 7;
 8 const int maxn = 3e3 + 10;
 9 int n, nxt[maxn][30], f[maxn];
10 char s[105];
11  
12 int dfs(int x) //记忆化搜索 
13 {
14     if(f[x])//如果以x为根的子树节点个数已经求得,直接用就好了 
15        return f[x];
16     for(int i=0; i<26; i++)
17         if(nxt[x][i]) f[x] += dfs(nxt[x][i]);
18     return ++f[x];//最后加上根节点,即空串 
19 } 
20  
21 int main() 
22 {
23     scanf("%d%s", &n, s+1);
24     for(int i=n; i; i--) 
25     {
26         for(int j=0; j<26; j++)
27           nxt[i-1][j] = nxt[i][j];
28         nxt[i-1][s[i]-a] = i;
29     }
30     int num = dfs(0);
31     printf("%d\n", num);
32 }

 

子序列计数

原文:https://www.cnblogs.com/cutepota/p/12667962.html

(1)
(1)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!