Bounds on the number of string subsequences
- Daniel S. Hirschberg
- Department Of Information
- Mireille Regnier Inria Rocquencourt
Publication date
January 1999
DOI Publisher
Springer-Verlag ISSN
0302-9743 Citation count (estimate)
12Abstract
ABSTRACT: The problem considered is that of determining the number of subsequences obtain-able by deleting t symbols from a string of length n over an alphabet of size s. Recurrences are proven and solved for the maximum and average case values, and bounds on these values are exhibited
Add to ORKG