Prague Stringology Conference 2021
Ryo Hirakawa, Yuto Nakashima, Shunsuke Inenaga and Masayuki Takeda
Counting Lyndon Subsequences
| Abstract: |
| Counting substrings/subsequences that preserve some property (e.g., palindromes, squares) is an important mathematical interest in stringology. Recently, Glen et al. studied the number of Lyndon factors in a string. A string w = uv is called a Lyndon word if it is the lexicographically smallest among all of its conjugates vu. In this paper, we consider a more general problem "counting Lyndon subsequences". We show (1) the maximum total number of Lyndon subsequences in a string, (2) the expected total number of Lyndon subsequences in a string, (3) the expected number of distinct Lyndon subsequences in a string. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |