Name
Abstract | ||
|---|---|---|
The longest Lyndon substring of a string T is the longest substring of T which is a Lyndon word. LLS(T) denotes the length of the longest Lyndon substring of a string T. In this paper, we consider computing LLS(Tu0027) where Tu0027 is an edited string formed from T. After O(n) time and space preprocessing, our algorithm returns LLS(Tu0027) in O(log n) time for any single character edit. We also consider a version of the problem with block edits, i.e., a substring of T is replaced by a given string of length l. After O(n) time and space preprocessing, our algorithm returns LLS(Tu0027) in O(l log sigma + log n) time for any block edit where sigma is the number of distinct characters in T. We can modify our algorithm so as to output all the longest Lyndon substrings of Tu0027 for both problems. |
Year | Venue | Field |
|---|---|---|
2018 | CPM | Discrete mathematics,Binary logarithm,Combinatorics,Substring,Computer science,Spacetime,Single character,Sigma,Lyndon word |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yuki Urabe | 1 | 0 | 0.68 |
| Yuto Nakashima | 2 | 57 | 19.52 |
| Shunsuke Inenaga | 3 | 595 | 79.02 |
| Hideo Bannai | 4 | 620 | 79.87 |
| Masayuki Takeda | 5 | 9 | 13.78 |