moteur de recherche

Séminaire Algo - Thierry Lecroq
Séminaire Algo - Thierry Lecroq
30-Nov-2021 14:00
Age: 55 days





Thierry Lecroq

Cartesian Pattern Matching

Building Copernic, seminar room (4B125)

Abstract : Cartesian trees are associated to strings of numbers. They are structured as heap and original strings can be recovered by symmetrical traversal of the trees. Let x be a string of numbers of length m. The Cartesian tree of x is the binary tree where:

- the root corresponds to the index i of the minimal element of x (if there are several occurrences of the minimal element, the leftmost one is chosen);

- the left subtree of the root corresponds to the Cartesian tree of x[1..i-1];

- the right subtree of the root corresponds to the Cartesian tree of x[i+1..m]. Cartesian pattern matching can be applied to find patterns in time series data.

In this talk, we will review the existing Cartesian pattern matching algorithms and describe more in details solutions for the following problems:

- given a text and a pattern that consist of sequences of numbers, find all the substrings of the text that have the same Cartesian tree than the pattern;

- given a text and a finite set of patterns that consist of sequences of numbers, find all the substrings of the text that have the same Cartesian tree than one of the patterns.

- given two strings that consist of sequences of numbers, find the length of the longest substring of both strings that have the same Cartesian tree.








<- Back to: Accueil