@article{oai:ipsj.ixsq.nii.ac.jp:00206700,
 author = {Kazuya, Tsuruta and Dominik, Köppl and Yuto, Nakashima and Shunsuke, Inenaga and Hideo, Bannai and Masayuki, Takeda and Kazuya, Tsuruta and Dominik, Köppl and Yuto, Nakashima and Shunsuke, Inenaga and Hideo, Bannai and Masayuki, Takeda},
 issue = {2},
 journal = {情報処理学会論文誌数理モデル化と応用（TOM）},
 month = {Aug},
 note = {We introduce a new class of straight-line programs (SLPs), named the Lyndon SLP, inspired by the Lyndon trees (Barcelo, 1990). Based on this SLP, we propose a self-index data structure of O(g) words of spacethat can be built from a string T in O(n lg n) expected time, retrieving the starting positions of all occurrences of a pattern P of length m in O(m + lg m lg n + occ lg g) time, where n is the length of T, g is the size of the Lyndon SLP for T, and occ is the number of occurrences of P in T., We introduce a new class of straight-line programs (SLPs), named the Lyndon SLP, inspired by the Lyndon trees (Barcelo, 1990). Based on this SLP, we propose a self-index data structure of O(g) words of spacethat can be built from a string T in O(n lg n) expected time, retrieving the starting positions of all occurrences of a pattern P of length m in O(m + lg m lg n + occ lg g) time, where n is the length of T, g is the size of the Lyndon SLP for T, and occ is the number of occurrences of P in T.},
 pages = {84--92},
 title = {Grammar-compressed Self-index with Lyndon Words},
 volume = {13},
 year = {2020}
}