On the Number of Subsequences When Deleting Symbols From a String
2008
We consider the problem of finding the number of subsequences when deleting symbols from a string. We present a framework to find closed-form expressions for the number of subsequences, and use it to prove the first explicit formulas for and the first formulas for nonbinary alphabets. We also present the first efficient algorithm to compute the number of subsequences for any string, number of deletions, and alphabet size.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
9
References
17
Citations
NaN
KQI