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: |