算法二十七：子序列

作者：盐析白兔 | 2024-08-20 03:02:34

踩

子序列

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

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

输入一个字符串。

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

ababc

有这些子序列：

a，b，c，aa，ab，ac，ba，bb，bc，aba，abb，abc，aab，aac，bab，bac，bbc，abab，abac，abbc，aabc，babc，ababc

[令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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/1004879