子序列

子序列

描述

给定一个字符串，求出该字符串有多少不同的子序列。

子序列：字符串中按顺序抽出一些字符得到的串。比如字符串 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;

}