Finding Periods in Cartesian Tree Matching

摘要

In Cartesian tree matching, two strings match if the Cartesian trees of the strings are the same. In this paper we define full, initial, and general periods in Cartesian tree matching, and present an O(n) time algorithm for finding all full periods, an O(n log log n) time algorithm for finding all initial periods, and an O(n log n) time algorithm for finding all general periods of a string of length n.