Prague Stringology Conference 2020
Simone Faro, Thierry Lecroq and Kunsoo Park
Fast Practical Computation of the Longest Common Cartesian Substrings of Two Strings
| Abstract: |
| Cartesian trees have been introduced 40 years ago. They are associated to strings of numbers. They are structured as heap and original strings can be recovered by symmetrical traversal of the trees. The Cartesian tree matching problem appeared very recently. It consists of finding all substrings of a given text which have the same Cartesian tree as that of a given pattern. Here we present two methods for computing the longest common Cartesian substrings of two strings. The first method is a classical linear suffix tree based method. The alternative method runs in quadratic worst case time but is more space economical. Experiments show that the alternative solution runs faster for short strings. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |