子序列发表时间:2022-10-27 20:30 子序列 描述 给定一个字符串,求出该字符串有多少不同的子序列。 子序列:字符串中按顺序抽出一些字符得到的串。比如字符串 abcd 里,ab、ac、ad、 abc、acd 都是子序列。 输入 输入一个字符串。 输 输出不同的子序列的个数除以 23333 得到的余数。 样例 1 输入 样例 1 输 样例 1 解释 有这些子序列: a,b,c,aa,ab,ac,ba,bb,bc,aba,abb,abc,aab,aac,bab,bac,bbc, abab,abac,abbc,aabc,babc,ababc 样例 2 请查看下发文件内的 sample2_input.txt 和 sample2_output.txt。 限制 对于 50%的数据,字符串长度不超过 15; 对于 100%的数据,字符串长度不超过 500000。字符串为 26 个小写字母组成。 时间:2 sec 空间:512 MB 提示 [令 f(i)f(i)为前 ii 中本质不同的的子序列个数,令 pre(i)pre(i)表示字符 sisi 之前出现的位置,则] [f(i)={f(i−1)+f(i−1)+1pre(i)=0f(i−1)+f(i−1)−f(pre(i)−1)pre(i)≠0] [答案等于 f(n)f(n).] 代码 #include <bits/stdc++.h> #include<string> using namespace std; // ================= 代码实现开始 ================= const int N = 500005, mo = 23333; int f[N], p[N], last[26]; // 为了减少复制开销,我们直接读入信息到全局变量中 // s:题目所给字符串int n; char s[N]; // 求出字符串s有多少不同的子序列 // 返回值:s不同子序列的数量,返回值对mo取模int getAnswer() { for (int i = 1; i <= n; ++i) { int a = s[i] - 'a'; p[i] = last[a]; last[a] = i; } f[0] = 0; for (int i = 1; i <= n; ++i) { f[i] = (p[i] == 0) ? (f[i - 1] + f[i - 1] + 1) : (f[i - 1] + f[i - 1] - f[p[i] - 1]); f[i] %= mo; } return (f[n] + mo) % mo; } // ================= 代码实现结束 ================= int main() { scanf("%s", s + 1); n = strlen(s + 1); printf("%d\n", getAnswer()); return 0; } |