TSOJ - 子序列 (DP 字符串)

xiaoxiao2021-02-28  10

子序列 (DP 字符串)

题目链接: 子序列


题目信息

描述

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

子序列:字符串中按顺序抽出一些字符得到的串。比如字符串abcd里,ab、ac、ad、abc、acd都是子序列。

输入

输入一个字符串。

输出

输出不同的子序列的个数除以23333得到的余数。

样例1输入

ababc

样例1输出

23

样例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个小写字母组成。


思路

注意取模!(算式中出现了减法,简单取模会出现异常情况)


代码

#include <bits/stdc++.h> using namespace std; const int MAXN = (int)5e5+1; char str[MAXN]; int f[MAXN]; int pre[200]; int main() { scanf("%s",str+1); int len = strlen(str+1); for (int i = 1;i <= len;i ++){ if (pre[str[i]] == 0) f[i] = f[i-1] + f[i-1] + 1; else f[i] = f[i-1] + f[i-1] - f[pre[str[i]]-1] + 23333; pre[str[i]] = i; f[i] %= 23333; } printf("%d\n",f[len]); }
转载请注明原文地址: https://www.6miu.com/read-2250171.html

最新回复(0)