Abstract A Cartesian tree is associated with a string of numbers and is structured as a heap from which the original string can be recovered. Although Cartesian trees have been introduced 40 years ago, the Cartesian tree matching problem appeared very recently. It consists in finding all substrings of given text, which have the same Cartesian tree as that of a given pattern. In this paper, we address the problem of computing the longest common Cartesian substrings of two strings and present three methods for such problem. Our first method is based on a classical suffix tree construction and solves the problem in randomized linear time and linear space, although the space overhead is quite prohibitive in the case of large strings. Our second solution is based on classical dynamic programming, and our third solution is based on a constructive approach. Both of them run in quadratic worst case time but are more space economical in practice. From our experimental results, it turns out that our second solution runs faster than the standard suffix tree solution for short strings, whereas our third solution is more suitable for large strings, when storing a full suffix tree becomes prohibitive.

Assisting code evolution (refactoring, adaptation, parallelisation, etc.) can be handy for improving code quality and execution speed. Generally, tools assisting developers are tailored to some language, making analyses approaches hard to be applied in practice when using a different language. In this paper, we propose a cross-language framework for implementing analyses on object-oriented code. By separating the logic for computing metrics, or detecting code smells, that lets us identify the need for improvements, from code exploration, we enable developers designing high-level recommendation tools that can be effectively applied on the most common object-oriented languages, such as e.g. Java and C++. Code exploration components will provide inspection and data commonly needed for representing the details of the code, such as control and data dependencies, or object and method lists. These will be language-specific and provided by the framework itself.